# A counting problem related to twin primes

Update:

The chat room for this question: http://chat.stackexchange.com/rooms/69953/discussion-between-fedja-and-abiessu

The problem statement remains unchanged (below).

Consider the following problem:

Given the following sets with $u \in\Bbb Z^+$: \begin{align}A_u&=\{x^2:x\in [2^{u-1},2^u-1],\exists s,t \in\Bbb Z^+ : x^2=s^3+2s^2+st+t\}\\B_u&=\{x^2:x\in [2^{u-1},2^u-1],\exists s,t \in\Bbb Z^+ : x^2=2s^3+2s^2+2st+t\}\end{align}

prove that $\exists N\in\Bbb Z^+$ such that $\forall u\gt N, |A_u|\ge|B_u|$.

Edit: it has been pointed out that this problem directly correlates with the Twin Primes conjecture. This does not change the question.

My approach is to rearrange the specifier equations as follows (using $s_A,t_A,s_B,t_B$ to differentiate the sets):

$$x^2=(s_A+1)(s_A^2+t_A)+s_A^2\\ y^2=(2s_B+1)(s_B^2+t_B)+s_B^2$$

From here, it is almost "obvious" that the problem statement should be correct, and I take the path of letting $s_A=2s_B$ for all but $s_A=1$ and comparing counts of values for each such pairing. Once I have counted all the differences where $s_A=2s_B$, then I go back and count all the overlaps between $s_A=1$ and $s_A\gt 1$. When all of this is done, I get a value $N=45$ (which I am certain could be improved).

Is there a more effective or efficient approach? With such an "obvious" problem statement, it seems like there should be an easier way to get the required results...

I glossed over the details above, but the counting of actual results goes like this: for each value of $s_A=2s_B$ where $s_A+1$ is prime, there are exactly two possible solutions of the congruence $s_A^2\equiv x^2\pmod{s_A+1}$, and there are exactly two possible solutions of $s_B^2\equiv x^2\pmod{2s_B+1}$. These solutions exist for both congruences. Therefore the arithmetic sequences in $t_A,t_B$ given by $(s_A+1)t_A+(s_A+2)s_A^2$ and $(2s_B+1)t_B+(2s_B+2)s_B^2$ each produce the same number of values $x^2,y^2$ within a given interval whenever $s_A+1=2s_B+1$, up to a maximum difference of two values produced (per prime value $s_A+1$). The squarefree non-prime values of $s_A+1$ account for double-counted values, and if we account all the "maximum difference of two" possibilities in favor of $B_u$, we should effectively count the number of values that $s_A\gt 1$ can take on which affect the given interval and multiply it by $2$ as the "worst case" for the value of $|B_u|$. For the overlap counting between $s_A=1$ and $s_A\gt1$, we account for the "worst case" by taking the fact that $s_A+1=2$ covers all odd squares within any interval for $u\gt 5$, then multiply this result by all the overlap possibilities for each prime greater than $2$ up to the maximum possible value of $s_A+1$ as $\left(1-\frac 23\right)\left(1-\frac 25\right)\dots\left(1-\frac 2p\right)$, at which point we apply the result

$$\left(\prod_{p=3}^n\left(1-\frac 2p\right)\right)^{-1}=\frac 14e^{2\gamma}\Pi_2^{-1}\log^2n+O\left(e^{-c\sqrt{\log n}}\right)$$

This question is cross-posted from Math.SE (https://math.stackexchange.com/q/2521575/86846) following an intense period of no activity whatsoever.

• In other words, the OP has just found a fancy reformulation of the statement that the number of twin primes between $u-1$ and $2u-1$ is not larger than the number of twin primes between $2u-1$ and $4u-1$, called it "a small consideration", and posted it on MO in the hope that people will figure it out once the big name is detached. That's smart, but the problem is really hard even to somebody who cannot recognize it or has never heard of it. Normally I wouldn't spoil the fun, but attaching a bounty to it is a bit too much to my taste :lol: – fedja Dec 8 '17 at 21:09
• @fedja: I didn't attach this bounty, but I did attach one to the cross-post on Math.SE. This particular problem wasn't difficult once I knew that it needed to be solved, the difficulty was finding out that this was the problem that needed to be solved. – abiessu Dec 8 '17 at 21:22
• My verdict is: incomprehensible as written. You seem to believe that infinite products give exact counts rather than just asymptotics and use the phrase "proceeding the same way with other primes" with way too much liberty instead of defining the matching exactly and clearly. The only thing that was clear was that you did know that your question implied the twin prime conjecture. If you decide to rewrite your opus in a way more aligned with the standards of mathematical writing, I promise to give it one more try. As of now, I'd rather have my evening meal :-) – fedja Dec 9 '17 at 0:39
• – fedja Dec 9 '17 at 2:40
• Switch to chat. I feel it is not going to be short. – fedja Dec 9 '17 at 2:43

This is just to explain to everyone what is going on here.

The conditions are just $s+1|x^2-s^3-2s^2$ and $(2s+1)|4x^2-8s^3-8s^2$ (plus the positivity of the expressions on the right, i.e., roughly speaking, the inequality $s<x^{2/3}$).

Since $y^3\equiv -1$ and $y^2\equiv 1\mod y+1$, the divisibility conditions are just $s+1|x^2-1=(x-1)(x+1)$ and $2s+1|4x^2-1=(2x-1)(2x+1)$. Thus the numbers not in $A_u$ are those for which there are no divisors between $2$ and $x^{2/3}$ of either $x-1$ or $x+1$, i.e. those for which $x-1$ and $x+1$ is a twin prime pair. Similarly the numbers not in $B_u$ are the ones for which $2x-1$ and $2x+1$ is a twin prime pair. Since the complement of a larger set is smaller, we conclude that there are at least as many twin prime pairs $2x-1,2x+1$ as twin prime pairs $x-1,x+1$, when $x$ runs over $[u,2u-1]$, which is equivalent to saying that there are at least as many twin prime pairs in $[2u-1,4u-1]$ as in $[u-1,2u-1]$, so once we have at least one pair above $N$, we have it in every dyadic interval above that point giving the logarithmic growth of $\pi_2(n)$ at least.

• I see that you are "back" so to speak, so ping! once again... I've been waiting until I thought I had something worth reading. Mostly just the most recent couple days' worth of comments in the chat... the rest is me thinking out loud trying to get there. – abiessu Mar 30 '18 at 16:02
• @abiessu Yes, I'm partially back (one month later than I thought I would and still on and off, but back) :-) OK, I'll take a look at the chat, but a bit later. – fedja Mar 31 '18 at 1:48

Edit (5/3/18): A significant improvement to the comparison has been found. See the chat http://chat.stackexchange.com/rooms/69953/discussion-between-fedja-and-abiessu for more details.

The sieve function $x^2=s^3+2s^2+st+t$ in $A_u$ can be replaced with another function $x^2=m^4+mn+n$. This new function produces the same set $A_u$, but also allows many of the error terms to be reduced significantly.

Theorem: Given an integer $x\ge 4$, both $x-1$ and $x+1$ are prime if and only if $\forall m,n\in\Bbb Z^+,x^2\neq m^4+mn+n$.

Proof (Contraposition, only if): Assume that there is an $x\ge 4$ with either $x-1$ or $x+1$ non-prime. Note that $m^4-1=(m+1)(m-1)(m^2+1)$. First, suppose that $x+1$ is non-prime with factors $a,b$ where $ab = x+1$ such that $2\le a\le b$. Let $m+1=a$, then we have $m^4=(a-1)^4$ and $m^4-1+mn+n = (a-1)^4-1+an$. Since $a\le b$ we have $a^2\le x+1$ and $a^2-2\le x-1$ giving $a^4-2a^2\le x^2-1$. Finally, $(a-1)^4-1+a\le a^4-2a^2$ which lets $n$ take on any positive integer as needed such that $m^4+mn+n=x^2$. The same argument applies when $x-1$ is the composite number.

The "if" portion has no significant changes versus the argument for the previous sieve function.

Note that the set $B_u$ has a similar function replacement, but this is not strictly necessary as the set $A_{u+1,odd,even}$ (described below) contains a copy of the values that would be in $B_u$ but multiplied by $4$.

Partition the set $A_u$ into three subsets as follows:

• $A_{u,odd,odd}$ is the set of odd squares $x^2\in A_u$ such that there exists an odd value $m+1$ where $m^4+mn+n=x^2$ has at least one solution.
• $A_{u,odd,even}$ is the set of even squares $x^2\in A_u$ such that there exists an odd value $m+1$ where $m^4+mn+n=x^2$ has at least one solution.
• $A_{u,even}$ is the set of odd squares $x^2\in A_u$ such that $m+1=2$ provides the only possible solution to $m^4+mn+n=x^2$.

This partition of $A_u$ allows an identity $|A_u|=2^{u-2}+|B_{u-1}|$ which can also be stated as $|A_{u,odd,even}|=|B_{u-1}|$. It is noteworthy that $|A_{u,odd,odd}|$ should have an asymptotically similar value to $|A_{u,odd,even}|$. In particular, note that we must have $m^4\le 4^u-1\to m\le 2^{\frac u2}$ and let $$C_u=\left\{x^2:x\in \left[2^{u-1}-2^{\frac u2-\frac 12},2^u+2^{\frac u2-\frac 12}-1\right],\exists m,n \in\Bbb Z^+ : x^2=m^4+mn+n\right\}$$ be a non-partitioning indexed subset of the squared integers. Since $m\le 2^{\frac u2}$, we have that every odd $x^2\in C_u$ where $x^2\in A_{u-1,odd,odd}$ or $x^2\in A_{u+1,odd,odd}$ is one that could be counted as a "miss" by one of the sieves $(m+1)n+m^4=x^2$ acting on the interval $x^2\in [4^{u-1},4^u-1]$. The count of odd values $x\in [2^{u-1}-2^{\frac u2-\frac 12},2^u+2^{\frac u2-\frac 12}-1]$ such that $x\notin [2^{u-1},2^u-1]$ is $2^{\frac u2}$. Each of these squares may appear as a "count difference" between $|A_{u,odd,odd}|$ and $|A_{u,odd,even}|$, and therefore we have $\left||A_{u,odd,odd}|-|A_{u,odd,even}|\right|\le 2^{\frac u2}$. Adding in the negative space with $|A_{u,odd,odd}|+|A_{u,even}|=2^{u-2}$, we have

$$\left||A_u|+|A_{u,even}|-2^{u-1}\right|\le 2^{\frac u2}.$$

Conjecture: Using the principle of inclusion/exclusion, we can bound the value of $|A_{u,even}|$ by taking the number of odd squares which will not be part of any sieve for an odd value $m+1$ by $2^{u-2}\cdot(1-\frac 23)\cdot(1-\frac 25)\cdot(1-\frac 27)\cdots$, which gives the result $$2^{u-2}\prod_{p=3}^{2^{\frac u2}}\left(1-\frac 2p\right)=\frac {2^{u-2}}{\frac 14e^{2\gamma}\Pi_2^{-1}\log^22^{\frac u2}+O\left(e^{-c\sqrt{\log 2^{\frac u2}}}\right)}\\ \ge \frac {2^{u-2}}{u^2}.$$

Combining the previous results, this allows us to say that $2^{u-1}-|A_u|\ge \frac {2^{u-2}}{u^2}-2^{\frac u2}$. For $u\ge 17$, this says that there is a positive number of twin prime pairs present in the interval $[4^{u-1},4^u-1]$ where each pair is represented as $x-1,x+1\to x^2$ within this interval.

Many thanks to user fedja (https://mathoverflow.net/users/1131/fedja) for assisting me in working out this argument's details and helping me see the failings of previous approaches.

• Except it still doesn't hold water (see my last message in the chat). – fedja Dec 9 '17 at 5:54