**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...


Addendum:


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)$$


(from <https://math.stackexchange.com/a/22435/86846>).


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



A counting problem related to twin primes
**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.


