2
$\begingroup$

I want to solve a quadratic equation over the integers but the naive method is unbearably slow (considering how easy the problem is).

I have a positive non-degenerate quadratic form $Q$ on $\mathbb Z^n$(This is why I only have finitely many solutions) and I want to find all solutions of

$$Q(x)=a$$

With $a$ some fixed constant. In principle the problem is solved by

xx = Array[x, n]
Solve[Q[xx]==a,xx,Integers]

but this takes an insane amount of time even for small numbers (for instance $n=6$). Any ideas on how can I speed up the process?


A concrete example:

mat = {{4/3, 5/3, 2, 4/3, 2/3, 1}, {5/3, 10/3, 4, 8/3, 4/3, 2}, {2, 4,
     6, 4, 2, 3}, {4/3, 8/3, 4, 10/3, 5/3, 2}, {2/3, 4/3, 2, 5/3, 4/3,
     1}, {1, 2, 3, 2, 1, 2}};
Q[xx_] := xx . mat . xx;
xx = Array[x, 6];
Solve[Q[xx] == 26, xx, Integers]
$\endgroup$
5
  • 3
    $\begingroup$ Please include Mathematica code for a concrete example. It should be a simple example that illustrates the problem. $\endgroup$
    – user293787
    Aug 17 at 15:25
  • 1
    $\begingroup$ @user293787 just added an example :). $\endgroup$ Aug 17 at 15:39
  • 2
    $\begingroup$ For those wanting an example that completes in around 3 to 4 seconds, replace xx . mat . xx with xx . mat[[1 ;; 5, 1 ;; 5]] . xx and replace xx = Array[x, 6]; with xx = Array[x, 5];. $\endgroup$
    – JimB
    Aug 17 at 16:52
  • $\begingroup$ Are negative integers allowed? $\endgroup$
    – Carl Woll
    Aug 17 at 16:57
  • $\begingroup$ @CarlWoll hmmm I don't see how that simplifies the problem; but yes I am only interested in non-negative solutions, lets say negative integers are not allowed (in general mat can have negative entries though). $\endgroup$ Aug 17 at 17:01

1 Answer 1

5
$\begingroup$

In the case of the example, the code

(* OPs code *)
mat={{4/3,5/3,2,4/3,2/3,1},{5/3,10/3,4,8/3,4/3,2},{2,4,6,4,2,3},{4/3,8/3,4,10/3,5/3,2},{2/3,4/3,2,5/3,4/3,1},{1,2,3,2,1,2}};
Q[xx_]:=xx.mat.xx;
xx=Array[x,6];
val=26;

(* solve by fixing x[1], motivated by @JimB's comment *)
x1max=Floor[Sqrt[val*Inverse[mat][[1,1]]]];
auxsol[x1_]:=Solve[{x[1]==x1,Q[xx]==val},xx,Integers]//If[#==={},{},xx/.#]&;
sol=Join@@Table[auxsol[x1],{x1,-x1max,x1max}];

takes about 50 seconds, and finds all

Length[sol]
(* 12240 *)

integer solutions. Whether that is "unbearably slow" depends on the application.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer! unfortunately that might miss solutions. Your bound on x1 is not always satisfied as there could be negative numbers all around (for instance in the case at hand Inverse[mat] has negative entries). A bound which does work is the root of val/min(eigenvalue(mat)). Using this bound and your idea in all the other variables this boils down to simply checking every possible value up to some point which I don't believe is an optimal solution, do you think this is the best one can do? $\endgroup$ Aug 18 at 14:36
  • 1
    $\begingroup$ I disagree, the bound I use for x1 is safe: For all real vectors $x,y$ and positive definite $M$ one has $(y^Tx)^2 \leq (y^T M^{-1} y)(x^T M x)$ by Cauchy-Schwarz, then set $y = (1,0,\ldots,0)$. I cannot answer your question about optimality, but I'd encourage you to state precisely what "optimal" means for you. The answer depends on whether you are interested in increasing the size of mat, or keeping mat fixed and increase val, or running this for many mat of all the same size. If you state this more precisely in your post, perhaps someone can give your more detailed feedback. $\endgroup$
    – user293787
    Aug 18 at 15:38
  • $\begingroup$ Ah, I see thanks for the pf, I had completely missed it. $\endgroup$ Aug 18 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.