# Solve[] unexpectedly giving empty solution sets for extremely large problems

I was calculating the set of lattice vectors in $\mathbb{Z}^4$ which have taxicab norm $r$. For example, executing

Solve[Abs[c1] + Abs[c2] + Abs[c3] + Abs[c4] <= 2, {c1, c2, c3, c4}, Integers]


yields the 41 lattice vectors of taxicab norm 2 or less. This works fine up through $r=19$, at which point there are 97,281 solutions. However, at $r=20$,

Solve[Abs[c1] + Abs[c2] + Abs[c3] + Abs[c4] <= 20, {c1, c2, c3, c4}, Integers]


simply returns {{}}. According to the documentation, Solve[] yields {{}} "if the set of solutions is full-dimensional", which is clearly not the case for the above, which has a finite, though large, number of solutions.

Also, as far as I could tell, nowhere in the documentation does it specify that there is a cap on the number of possible solutions.

Question: Is there are a reason for this? And is there a way to coax Solve[] into returning the correct answer?

I know of the obvious though tedious mathematical tricks for reducing the problem into several lower-dimensional problems, but I'd like to solve it directly if possible.

• Mathematica also returns a Solve::fulldim warning. So Reduce should be used. You can find something useful here: forums.wolfram.com/mathgroup/archive/2010/Dec/msg00223.html – luyuwuli Dec 25 '13 at 1:22
• @luyuwuli: Thanks, but the point of my question was that the problem is not full-dimensional; I am aware of the difference between Solve[] and Reduce[]. The issue is that the Solve[] is giving an incorrect result, namely giving a full-dimensional output without generating a Solve::fulldim warning on a problem which is not full-dimensional. – DumpsterDoofus Dec 25 '13 at 1:25
• You'd better play with Reduce having set appropriate "ReduceOptions" -> "ExhaustiveSearchMaxPoints". You can find a good example here: Solving/Reducing equations in Z/pZ. It might be even more reasonable to make a neat use of FrobeniousSolve, here you can find an interesting example Finding the number of solutions to a diophantine equation. – Artes Dec 25 '13 at 1:30
• Thanks, I'll take a look at it as an alternate possibility! What's weird about my current method is that Solve[] and Reduce[] yield the same results for $r\leq 19$, but for $r\geq 20$ Solve[] is unable to give the correct answer, and does so without warning. – DumpsterDoofus Dec 25 '13 at 1:35
• Why not this instead?: crosspolytope[n_] := Flatten[Table[{c1, c2, c3, c4}, {c1, -n, n}, {c2, Abs[c1] - n, n - Abs[c1]}, {c3, Abs[c1] + Abs[c2] - n, n - (Abs[c1] + Abs[c2])}, {c4, Abs[c1] + Abs[c2] + Abs[c3] - n, n - (Abs[c1] + Abs[c2] + Abs[c3])}], 3] – Michael E2 Dec 25 '13 at 3:12