Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial time: $$ \sum_{i=1}^n a_ix_i^2=b$$ with $a_i, b\in\mathbb F$. Some discussion suggests, that the algorithmical model assumed in the paper is that of a machine that can perform field operations in one step.

My question is: What is the algorithm? Is it multidimensional Newton? That would be weird because this algorithm only converges (in some cases) and does not give an exact solution. I'm quite unused to computational models over fields like the reals or complex numbers and maybe for someone who is more experienced this is cristal-clear?

[1] Agrawal & Saxena, On the complexity of cubic forms, 2006.

  • 2
    $\begingroup$ Can't you just solve a system of linear equations in $x_i^2$? $\endgroup$ – JeffE Jul 11 '12 at 19:57
  • $\begingroup$ JeffE: This is not really a system of linear equations… $\endgroup$ – Tsuyoshi Ito Jul 12 '12 at 3:58
  • $\begingroup$ What do you mean by solve? For $\mathbb{F} = \mathbb{C}$, it is easy to find some solution by taking any $a_i \neq 0$, letting $x_i = \sqrt{b/a_i}$, and $x_j = 0$ for $j \neq i$. For $\mathbb{F} = \mathbb{R}$ we only have to be slightly more careful. Are you worried about calculating the square root? $\endgroup$ – Yuval Filmus Jul 12 '12 at 4:57
  • $\begingroup$ @Yuval: yeah, you are perfectly right really obvious... concerning the case of reals: is there an easy criterion for solvability? And the square root: I'm always a bit worried when it comes to working with reals ... but I think there is no better way than giving an algorithm that only converges to the square root. $\endgroup$ – born Jul 12 '12 at 8:51
  • $\begingroup$ All you need in the real case is that $b=0$, or at least one $a_i$ has the same sign as $b$ (so that $b/a_i$ is nonnegative). $\endgroup$ – Klaus Draeger Jul 12 '12 at 10:53

We assume that we are allowed to take square roots in $\mathbb{F}$.

$\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. If $b \neq 0$ and $a_1 = \cdots = a_n = 0$ then there is no solution. Otherwise, let $a_i \neq 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.

$\mathbb{F} = \mathbb{R}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. Otherwise, without loss of generality assume that $b > 0$ (otherwise, multiply all of $b,a_1,\ldots,a_n$ by $-1$). If $a_i \leq 0$ for all $i$ there is no solution. Otherwise, let $a_i > 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.

| cite | improve this answer | |
  • $\begingroup$ And what in the non-trivial case, i.e. the $x_i$ may not be zero? $\endgroup$ – Raphael Jul 17 '12 at 16:18
  • 1
    $\begingroup$ It's similar to the trivial case, just put $x_i = \epsilon$. $\endgroup$ – Yuval Filmus Jul 18 '12 at 5:49

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.