2

Matiyasevich's theorem says, all the computably enumerable integer sets are diophantine. Thus, a set of diophantine equations exists, whose solution (in any of their variables) are this set.

Now consider the set of the integer powers of two. It is clearly recursively enumerable.

Which diophantine equation could have this set as its solution?

First I would say, that it is impossible - diophantine equations are polynomial, and my naive first spot is that they can't have this set of solutions in any of their variables. But this contradicts the MRDP theorem.

GreginGre
  • 15,028
peterh
  • 2,683
  • You might want to see this very similar question: https://math.stackexchange.com/questions/415556/how-to-express-the-powers-of-two-by-a-diophantine-equation. Jones (cited in the answer) has done a lot of work on finding efficient Diophantine representations for interesting sets, but I'm not sure about powers of $2$ specifically. – Erick Wong Sep 20 '19 at 05:52
  • Note that a Pell equation is polynomial and already generates exponentially-growing sequences. So this can inform your intuition somewhat. Of course, powers of $2$ will not arise in a Pell equation, but you might ask yourself what property is special about powers of $2$ that makes it feel impossible to arise from a polynomial? – Erick Wong Sep 20 '19 at 22:06

1 Answers1

1

$n$ is a power of $2$ iff

$$\forall a\,\forall b\,(2\cdot a+1)\cdot b=n\to a=0. $$ So let's start with something like $$ ((2a+1)b-n)^2$$ which is $\ge 0$ with equality iff $(2a+1)b=n$. Now let's express that $a$ is a positive integer. By Lagrange's four-square-theorem, this is equivalent to $\exists c\exists d\exists e\exists f\,a=1+c^2+d^2+e^2+f^2$. Thus from $$ P(n;a,b,c,d,e,f):=((2a+1)b-n)^2+(1+c^2+d^2+e^2+f^2-a)^2$$ we see that the non-powers of $2$ are diophantine.

As $P$ is always non-negative, we arrive at the complement set by looking at $$ Q(n;a,b,c,d,e,f,g,h,i,j) := 1+g^2+h^2+i^2+j^2-P(n;a,b,c,d,e,f)$$

Hagen von Eitzen
  • 374,180
  • I didn't know this trick to get the complements. From a downvote to an upvote! – Wojowu Sep 08 '19 at 11:26
  • 3
    Could someone explain the complement trick to me? It seems to me that $Q$ should yield all of $\mathbb N$ by just picking $a$ through $f$ at random to make $P(n;a,\ldots,f)$ positive. – Erick Wong Sep 20 '19 at 04:54
  • 2
    I agree with @ErickWong - this doesn't seem right – Akiva Weinberger May 04 '20 at 06:12
  • 1
    @ErickWong Fixing your LaTeX (it rendered weirdly): "The polynomial $P$ is not identically $0$ (e.g. the coefficient of $f^4$ is 1). Thus there exists many choices of $a,\ldots,f$ that makes $P$ nonzero, hence positive. Thus $Q$ has an integer solution. But this means the Diophantine set defined by $Q$ consists of all $n$, not the powers of $2$." – Akiva Weinberger May 04 '20 at 20:35
  • @AkivaWeinberger Thanks for the corrected repost! I’ll delete my above comment in case it is causing rendering issues elsewhere, and you have restated it accurately. – Erick Wong May 05 '20 at 02:06