# A counting problem related to the Twin Primes conjecture

Consider the following problem:

Given the following sets where $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|$.

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 approach seems wrong in terms of being "messy" and "informal", but I don't know how to improve it. Any suggestions?

Cross-posted to MathOverflow (https://mathoverflow.net/questions/286967) following a significant lack of interest here.

• are $x,s,t,u$ positive integers ? Dec 5, 2017 at 0:49
• @mercio yes they are. Dec 5, 2017 at 2:24
• sometimes I feel that there are problems that are "messy" and "informal" the first thing I am going to try is to present the counting process you describe in the addendum (if possible) as a series of piecewise expressions, so that I can get a more clear picture algorithmically Feb 25, 2020 at 7:12
• The approach I took to a problem I had similar to your question involved finding an algebraic expression that are a function of (in this case $u$) for the ratio of the cardinalities of the two sets, then finding the same for the individual cardinalities based on some assumptions of the existence of a posited equivalence relation for which they are disjoint subsets of a super set. This problem is I suspect far more complex than mine, so the approach may not be of any value here Feb 25, 2020 at 7:17

After some good discussion over the question as cross-posted to MathOverflow, there were many improvements found.

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.

• my apologies I hadn't scrolled down to see the answer when I commented before Feb 25, 2020 at 7:20
• @AdamL: no worries, I've made further progress since this was posted, there are still a few gaps between here and completing the proof... Feb 26, 2020 at 22:20
• Cool no drama bud can I ask why do you have partition elements defined for a range of $x$ ie it can be elements of a multiset for example $x\in \left[2^{u-1}-2^{\frac u2-\frac 12},2^u+2^{\frac u2-\frac 12}-1\right]$ like isn't the statement of a twin prime pair existing in interval $[4^{u-1},4^u-1]$ a paraphrasing of the twin prime conjecture? Feb 28, 2020 at 14:08
• @AdamL: That's exactly true... some of this is a search for a restatement that may be easier to prove... Feb 29, 2020 at 18:17