5
$\begingroup$

Is there an algorithm to decide whether a closed-form expression over integer variables using, say, $\{+,-,\times,\div,\text{^},\lfloor\text{lg}\rfloor,!,()\}$, or some other useful set of operators, is everywhere zero?

For example, is $(jk)^2 +k!-2j$ always 0 when $j,k$ are integers (obviously not)? If some of the operators make it impossible, is it possible with just a subset, for example if one removes factorial?

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 12 '16 at 7:32
  • 2
    $\begingroup$ Do you know Richardson theorem? If this problem is solvable (on defined operations) there should be canonical form, expansion, series representation, that you could show identity, but for some problems this cannot be done. Do you consider also integrals and polynomials? $\endgroup$ – Evil Mar 12 '16 at 21:41
  • $\begingroup$ @EvilJS from the operations I included, you can see I consider polynomials; I don't count integrals because I'm only interested in functions from integers to integers. $\endgroup$ – Elliot Gorokhovsky Mar 12 '16 at 21:42
  • 1
    $\begingroup$ 1. There's a heuristic: test at random values. It won't work for everything -- I imagine there are some expressions that are zero almost everywhere but not everywhere -- but I suspect it will often work well. 2. For some operators (e.g., $+, -, \times$), there is another heuristic: pick a random prime $p$, and evaluate the value of your expression modulo $p$ at random values. (This can help avoid the need to deal with huge numbers, by allowing modular reduction of intermediate values.) $\endgroup$ – D.W. Mar 13 '16 at 1:15
  • $\begingroup$ @D.W. I'm interested in exact solutions because I want to pass this to a SAT solver $\endgroup$ – Elliot Gorokhovsky Mar 13 '16 at 1:34
1
$\begingroup$

To decide if a particular diophantine equation (i.e., an expression in integers using multiplication and addition/subtraction equated to zero) has any solutions is undecidable. This is essentially the answer to the negative to Hilbert's tenth problem, which asks for an algorithm to determine if a diophantine equation has a solution.

$\endgroup$
  • $\begingroup$ You have to explain the reduction. $\endgroup$ – Yuval Filmus Mar 13 '16 at 0:08
  • 3
    $\begingroup$ This is a completely different question, we ask if it is possible to set the variables to make the expression not equal to 0. It is neither equivalent to the Diophantine problem or its complement. $\endgroup$ – Elliot Gorokhovsky Mar 13 '16 at 0:10
0
$\begingroup$

p=q has a solution if and only if 0^((p-q)*(p-q)) is not identically zero. ​ Thus, by undecidability of Diophantine equations, there is no such algorithm.


0^0 = 1 ≠ 0 ​ and for all positive x, ​ 0^x = 0 . ​ ​ ​ (p-q)(p-q) is a square, and thus never negative, so 0^((p-q)(p-q)) can be non-zero is and only if (p-q)*(p-q) can be zero. ​ ​ ​ Therefore

p=q has a solution
if and only if
p-q = 0 ​ has a solution
if and only if
p-q can be zero
if and only if
p-q can be zero
if and only if
(p-q)(p-q) can be zero
if and only if
0^((p-q)
(p-q)) can be non-zero

.

$\endgroup$
  • $\begingroup$ Thanks for the edit. But, oh dear, I was actually asking about why the 2nd sentence follows from the 1st, not why the 1st sentence is true. Sorry to have put you up to so much work explaining why the first sentence is true.. $\endgroup$ – D.W. May 13 '16 at 8:13

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.