14
$\begingroup$

Let $\mathbb N=\{0,1,2,\ldots\}$. Recall that the triangular numbers are those natural numbers $$T_x=\frac {x(x+1)}2\quad \text{with}\ x\in\mathbb N.$$ As $T_x=\binom{x+1}2$, Gauss' triangular number theorem (first claimed by Fermat) can be restated as follows: $$\left\{\binom x2+\binom y2+\binom z2:\ x,y,z\in\mathbb N\right\}=\mathbb N.$$

In view of the above, here I pose a conjecture on representations of integers involving binomial coefficients.

2-4-6-8 Conjecture. Any positive integer $n$ can be written as $$\binom{w}2+\binom{x}4+\binom{y}6+\binom{z}8\quad \text{with}\ w,x,y,z\in\{2,3,\ldots\}.$$

Observe that $$\frac12+\frac14+\frac16+\frac18=\frac{25}{24}\approx 1.0416667.$$ I have verified the above conjecture for all $n=1,\ldots,3\times10^7$. For example, $$4655=\binom{85}2+\binom{14}4+\binom 96+\binom 78=\binom{94}2+\binom 74+\binom 96+\binom{11}8$$ and $$192080=\binom{7}2+\binom{26}4+\binom{25}6+\binom{9}8=\binom{414}2+\binom{39}4+\binom 86+\binom{17}8.$$ See http://oeis.org/A306477 for related data. Note that $1061619$ is the first positive integer not representable as $\binom w2+\binom x4+\binom y6+\binom z9$ with $w,x,y,z\in\mathbb N$.

Question: Are there references in the literature to this or similar conjectures? What are some possible lines of attack for such problems?

I also have some other similar conjectures. See http://oeis.org/A306460, http://oeis.org/A306462 and http://oeis.org/A306471. For example, I conjecture that $$\left\{\binom{2x}2+\binom y2+\binom z3:\ x,y,z=1,2,3,\ldots\right\}=\{1,2,3,\ldots\}$$ and $$\left\{2\binom w3+\binom x3+\binom y3+\binom z3:\ w,x,y,z\in\mathbb N\right\}=\mathbb N.$$ The last equality implies Pollock's conjecture which states that any positive integer is the sum of at most five tetrahedral numbers.

Your comments are welcome!

Edit: The 2-4-6-8 conjecture has been verified for $n$ up to $5\times10^{11}$ by Yaakov Baruch, and for $n$ up to $2\times10^{11}$ by Max Alekseyev. I'd like to offer 2468 US dollars as the prize for the first correct proof of the 2-4-6-8 conjecture, or 2468 RMB as the prize for the first explicit counterexample.

Edit (March 12, 2019): Today Yaakov Baruch reported that he had verified the 2-4-6-8 conjecture for $n$ up to $2\times 10^{12}$ with no counterexample found.

$\endgroup$
  • 5
    $\begingroup$ mathoverflow.net/help/on-topic "MathOverflow is not the right place to ask open problems.... If you want to contribute to (or view) a list of open problems, visit the Open Problem Garden." $\endgroup$ – Zach Teitler Feb 19 at 7:02
  • 14
    $\begingroup$ On the contrary, I feel that the present question is perfect for MathOverflow. $\endgroup$ – Wlod AA Feb 19 at 16:48
  • 5
    $\begingroup$ I'm grateful to Prof. Max Alekseyev and Yaakov Baruch for checkng the conjecture. I'd like to offer 2468 US dollars as the prize for the first correct proof of the 2-4-6-8 conjecture. $\endgroup$ – Zhi-Wei Sun Feb 24 at 14:13
  • 5
    $\begingroup$ Verified up to $5\times 10^{11}$. That took 58G of memory on a machine with 52G, and 190 minutes, of which 23m system, presumably mostly swapping. So I think I reached my limit. Will be happy to give my code to anyone with better resources. $\endgroup$ – Yaakov Baruch Feb 26 at 23:35
  • 8
    $\begingroup$ Meta discussion: meta.mathoverflow.net/questions/4125/… (I request voting up this comment for visibility). I took the liberty of editing the question to implement some suggestions there. $\endgroup$ – Todd Trimble Mar 4 at 13:15
10
$\begingroup$

2-4-6-8, this we don't appreciate!

There is a long tradition of exploring additive representations of integers by polynomial sequences. The gold standard for measuring such progress is Waring's problem, but the circle method of Hardy and Littlewood to understand such problems works in many related situations. In particular, one could use the circle method to flesh out a conjectural asymptotic formula for problems such as the one in this question. Many of these problems, including the current one, are beyond the reach of current analytic machinery.

To gain a sense of what is feasible, let us return to Waring's problem. If one wishes to express $n$ as a sum of $s$ $k$-th powers, then if there are no local obstructions one expects this to be possible if $s \ge k+1$. However the circle method has any hope of working only if $s \ge 2k+1$ -- this is because even if one had square-root cancelation in the exponential sums over minor arcs, then one would need $s>2k$ for the main term to dominate the error terms. In reality, we are far from this barrier, and one can only prove that $s\ge (1+o(1)) k\log k$ variables suffice. A key exception is the situation of sums of squares -- plain vanilla circle method needs five variables, the Kloostermann refinement of the circle method allows for sums of four variables, and the connection with modular forms/theta functions allows for three variables. The case of squares, where we can do better than the limitations of the circle method, is very special.

Now for a variant of Waring's problem more closely connected to the present question. Roth considered first the problem of writing numbers as the sum of a square, a cube, a fourth power and so on. Roth established that almost all integers up to $x$ may be written as a sum of a square, a cube and a fourth power. This is the best possible result of its kind, because $1/2+ 1/3 < 1 < 1/2+ 1/3 +1/4$. If one asks for all large numbers being represented by an expression of this kind, then the best result known is due to Ford, who showed that all large $n$ are of the form $$ \sum_{i=2}^{k} x_i^i, $$ with $k=15$ being permissible. To compare this with the limitation on the circle method in Waring's problem mentioned above, the relevant quantity is $1/2+1/3+ \ldots +1/k$, and whether this is $>2$. It must be clearly be $>1$ for there to be solutions for all large $n$, and square-root cancelation in minor arc exponential sums would solve the problem if the sum of reciprocals exceeds $2$. This barrier would be crossed at $k=11$, and this gives some rough sense of Ford's work.

The problem here is of the flavor of writing $n$ as $$ \sum_{i=1}^k x_i^{2i}, $$ which is even worse than above. The threshold $\sum_{i=1}^{k} 1/(2i) >2$ is crossed when $k=31$ -- that is, the 2-4-6-8-10-12-...-62 conjecture is the most that circle method aficionados would dream of!

A more reasonable problem would be to ask for almost all integers being represented, in the spirit of Roth. See work of Laporta and Wooley in this (general) context, which will provide further references.

$\endgroup$
  • 2
    $\begingroup$ @Wojowu: No; my point is that one needs the sum to be $>2$ in order to have any hope! In each situation, what is known would vary depending on our knowledge of the relevant exponential sums. $\endgroup$ – Lucia Mar 9 at 22:19
  • 1
    $\begingroup$ I know the limitation of the circle method. If the 2-4-6-8 conjecture could be easily proved by the current circle method without creative innovation, I would not promise $2468 prize for its proof. $\endgroup$ – Zhi-Wei Sun Mar 10 at 1:18
  • 5
    $\begingroup$ I'm holding this problem to a high standard because the OP is a professional mathematician, and should be aware of the background for such problems. There are of course a lot of amateurs posing problems on MO. But from a professional mathematician, I imagine that there is some particular reason that you find this interesting, and I would like to understand what that is. I am not intending to be offensive, and of course you should feel free to ignore my answer or my comments. $\endgroup$ – Lucia Mar 10 at 1:37
  • 3
    $\begingroup$ "I'm only interested in writing every (not sufficiently large) $n\in\mathbb{N}$ in a desired form". But why? That is the question that several people, including myself, would like to know the answer to. What would it teach you about numbers if you knew that some particular a priori obviously fairly dense set contains all integers, rather than all with, say, one exception? $\endgroup$ – Alex B. Mar 10 at 9:33
  • 2
    $\begingroup$ I don't want to argue with anyone here. Different people have different viewpoints. For example, if Goldbach's conjecture only holds for even numbers greater than $10^{100}$, it would not be so famous. Usually people like concise results or conjectures. $\endgroup$ – Zhi-Wei Sun Mar 10 at 12:05
8
$\begingroup$

Not an answer - but I decided to delete a prior comment and repost as an answer, because I think it puts the 2-4-6-8 conjecture in a different light than considered so far, hopefully leading to some of the experts providing deeper insights and perhaps even a solution. So the stunning fact (to me) is this:

10 numbers up to $5\times 10^{10}$, besides $0$, were found to have a unique representation; they are $23343989$, $39866594$, $54847142$, $394239767$, $1769927927$, $2321530979$, $5022744494$, $7969623044$, $13295525747$, $14076782201$.

All of them are $\equiv 20\ (\textrm{mod}\ 33)$!

This I think points to a deeper arithmetic nature to the conjecture than it simply (likely) being true for "probabilistic" reasons.


UPDATE. I was wrong. As pointed out in the comments by StefanKohl and user21820, the anomaly described above can be fully explained by the fact that the $\equiv 20\ (\textrm{mod}\ 33)$ residue class appears with only 48.5% of the expected $\frac{1}{33}$ frequency. The next least frequent residue class is $9$, with 64% of the expected frequency. Since in the ranges considered, every number has more than 50 hits on average, that already makes the single hit probability millions of times higher for class $20$ than class $9$. I verified that also double, triple, etc. hits are quickly dominated by the $20$ residue class, followed far behind by the $9$.

Small upshot: a counterexample is most likely going to be $\equiv 20\ (\textrm{mod}\ 33)$ , and there are low-memory search algorithms that would be faster when restricted to that case. I'll post in the comments if/when I pursue that.

$\endgroup$
  • 1
    $\begingroup$ The 10 numbers are: $\binom{365}2+\binom{76}4+\binom{40}6+\binom{34}8$, $\binom{8167}2+\binom{58}4+\binom{43}6+\binom{9}8$, $\binom{8914}2+\binom{139}4+\binom{26}6+\binom{10}8$, $\binom{8693}2+\binom{240}4+\binom{43}6+\binom{45}8$, $\binom{57792}2+\binom{5}4+\binom{67}6+\binom{21}8$, $\binom{15456}2+\binom{341}4+\binom{93}6+\binom{53}8$, $\binom{99977}2+\binom{89}4+\binom{41}6+\binom{34}8$, $\binom{121487}2+\binom{346}4+\binom{39}6+\binom{16}8$, $\binom{155964}2+\binom{196}4+\binom{90}6+\binom{49}8$, $\binom{64714}2+\binom{584}4+\binom{134}6+\binom{31}8$. No visible patterns there... $\endgroup$ – Yaakov Baruch Mar 1 at 11:48
  • 1
    $\begingroup$ (continued:) 1450/35937, 1520/35937, 224/9801, 3364/107811, 460/11979, 248/9801, 3886/107811, 1180/35937, 208/9801, 232/11979, 370/11979, 100/3267, 4408/107811, 1120/35937, 232/9801, 1334/35937, 1240/35937, 268/9801, 3422/107811, 1040/35937, 16/1089, 1073/35937, 500/11979, 304/9801, 3248/107811, 1160/35937, 92/3267, 3596/107811, 1340/35937, 236/9801, 3016/107811, 80/3993, 74/3267. The minimum is at 20 modulo 33 (the value is 16/1089), which statistically explains that numbers having only one representation of the given form are typically congruent to 20 modulo 33. $\endgroup$ – Stefan Kohl Mar 1 at 18:04
  • 2
    $\begingroup$ Your facts presented in fact suggest the opposite (to your conclusion), namely that there is no deep reason for it to be true or false. The probabilistic heuristic and the empirical evidence suggests that the conjecture should be true for sufficiently large $n$. This means that whether or not there are counter-examples is a matter of small number coincidences. The congruence to $20$ mod $33$ should merely be an artifact of the residues of the binomial coefficients mod $33$, which less frequently sum to $20$. (Oh I just realized Stefan Kohl already stated my last point.) $\endgroup$ – user21820 Mar 2 at 15:32
  • 1
    $\begingroup$ @Yaakov Baruch In view of your observation, perhaps one should focus on checking the conjecture with $n\equiv 20\pmod{33}$. For $n>5\times10^{11}$ with $n\equiv20\pmod{33}$, do you have a quick way to check the conjecture for $n$? $\endgroup$ – Zhi-Wei Sun Mar 3 at 1:13
  • 1
    $\begingroup$ See comments to the original question for an updated search result (not based on any (mod 33) restriction). $\endgroup$ – Yaakov Baruch Mar 12 at 19:42

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.