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

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

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.

  • $\begingroup$ are $x,s,t,u$ positive integers ? $\endgroup$
    – mercio
    Dec 5, 2017 at 0:49
  • $\begingroup$ @mercio yes they are. $\endgroup$
    – abiessu
    Dec 5, 2017 at 2:24
  • $\begingroup$ 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 $\endgroup$ Feb 25, 2020 at 7:12
  • $\begingroup$ 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 $\endgroup$ Feb 25, 2020 at 7:17

1 Answer 1


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.

  • $\begingroup$ my apologies I hadn't scrolled down to see the answer when I commented before $\endgroup$ Feb 25, 2020 at 7:20
  • $\begingroup$ @AdamL: no worries, I've made further progress since this was posted, there are still a few gaps between here and completing the proof... $\endgroup$
    – abiessu
    Feb 26, 2020 at 22:20
  • $\begingroup$ 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? $\endgroup$ Feb 28, 2020 at 14:08
  • $\begingroup$ @AdamL: That's exactly true... some of this is a search for a restatement that may be easier to prove... $\endgroup$
    – abiessu
    Feb 29, 2020 at 18:17

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.