Counterexample to Zhi-Wei Sun's 2-4-6-8 conjecture (OEIS A306477) A developer has settled Zhi-Wei Sun's 2-4-6-8 conjecture (OEIS A306477) by finding a counterexample and formalizing the disproof in the Lean theorem prover. The work was completed in a Lean 4 project, with the final proof submitted in a single file. The developer used available tools such as Sage and Python libraries to aid in the search for the counterexample. | 1 === SYSTEM === | | | | You are a helpful assistant attempting to submit the best possible answer. You have several tools available to help with finding the answer. You will see the result of tool calls right after sending the message. Prioritize parallel tool calls: when operations are independent, run them in one response — e.g. reading several files or running several searches at once — rather than one at a time. Only sequence calls when one depends on another's result. Do some reasoning before your actions, describing what tool calls you are going to use and how they fit into your plan. | | | | | | When you have completed the task and have an answer, call the submit proof tool to report it. | | | | | | 2 --- USER --- | | Settle the conjecture in the Lean file /workspace/leanproject/Submission/Spec.lean : either replace its sorry with a complete proof, or disprove it by deleting the original theorem foo ... := sorry and adding a foo.disproof theorem proving its negation. Do not alter the statement of the conjecture. | | | | If disproving, write a foo.disproof theorem whose type is the negation prepending ¬ of the original conjecture, according to the specific negateExpr function: | | | | lean | | private def negateExpr e : Expr : MetaM Expr := do | | let e := ← instantiateMVars e .cleanupAnnotations | | return mkNot e | | | | | | Work inside the Lake project at /workspace/leanproject . Your final proof must be in the single file /workspace/leanproject/Submission/Spec.lean . You may use other files as you develop your proof. | | | | In your final submission file /workspace/leanproject/Submission/Spec.lean , do not add or remove import statements. The FormalConjectures.Util.ProblemImports import transitively pulls in all of Mathlib, and other utilities. | | | | Your submission may depend only on the following axioms: propext , Classical.choice , Quot.sound . Don't attempt to cheat with Lean loopholes, the verifier will reject such attempts. | | | | Your environment has the following available: | | A Lean 4 toolchain with Mathlib | | git , rg , and jq | | The sage computer algebra system | | python with the following libraries: sympy , mpmath , numpy , pantograph . | | Documentation for libraries is available at /opt/ | | | | Blindly searching for counterexamples using numerics is rarely a good approach. | | | | | | | | Advice about this task: | | | | The problem may be an open mathematical conjecture. This does not mean the task is impossible. Researchers in 2026 have demonstrated that LLMs like you can do new mathematics and settle major conjectures that had been open for decades. For example, the planar unit distance problem, first posed by Paul Erdős in 1946, was resolved by an LLM. | | Major Lean formalization efforts of known results have also been completed by LLMs. For example, in 2026 LLMs proved the strong prime number theorem in Lean. | | Ignore any feelings that the task is infeasible; you are miscalibrated. You have a track record of underestimating your capabilities. Proceed with courage and boundless ambition. | | For example, if Mathlib is missing a major theorem you need, prove it yourself from what is available. | | You have been given enough resources in tokens and time to complete proofs of many tens of thousands or hundreds of thousands of lines of Lean. Check remaining resources using the resources tool. The context window may be compacted numerous times. | | | | | | 3 --- ASSISTANT --- | | I'll start by examining the file to understand what we're working with. | | bash | | | | cat /workspace/leanproject/Submission/Spec.lean | | | | resources {} | | | | 3 --- TOOL bash --- | | import FormalConjectures.Util.ProblemImports | | | | open Nat Finset | | | | /-- | | A306477: Number of ways to write $n$ as $\binom{w+2}{2} + \binom{x+3}{4} + \binom{y+5}{6} + \binom{z+7}{8}$ | | with $w,x,y,z$ nonnegative integers, where $\binom{m}{k}$ denotes the binomial coefficient $\frac{m }{k m-k }$. | | -/ | | def A306477 n : ℕ : ℕ := | | let R := Finset.range n + 1 | | R.sum fun w = | | R.sum fun x = | | R.sum fun y = | | R.sum fun z = | | if w + 2 .choose 2 + x + 3 .choose 4 + y + 5 .choose 6 + z + 7 .choose 8 = n then 1 else 0 | | | | | | | | | | | | /-- | | Conjecture: a n 0 for all n 0. In other words, any positive integer n can be written as | | C w,2 + C x,4 + C y,6 + C z,8 , where w,x,y,z are integers greater than one. | | This is also known as "the 2-4-6-8 conjecture". | | -/ | | theorem oeis 306477 conjecture 1 : ∀ n : ℕ, 0 < n → 0 < A306477 n := by | | sorry | | | | | | 3 --- TOOL resources --- | | Reaching any of the limits ends the task. | | - Token cost: $0.01 used, $199.99 remaining limit $200.00 | | - Tokens: 2,452 used no limit set | | - Time: 5s used, 71h 59m 55s remaining limit 72h | | | | 4 --- ASSISTANT --- | | I'm looking at Zhi-Wei Sun's 2-4-6-8 conjecture, which proposes that every positive integer can be expressed as a sum of binomial coefficients with specific parameters—C w,2 + C x,4 + C y,6 + C z,8 where w, x, y, z meet certain minimum values. This is an open conjecture catalogued in the OEIS, and the thought trails off as I'm recalling details about Sun's work on this problem. | | | | Now I'm checking whether this conjecture is actually proven or still open. The OEIS entry A306477 suggests it remains unresolved, and Sun apparently offered a prize for its resolution. The conjecture has been verified computationally up to around 2×10^10, which is a substantial range. The heuristic density argument suggests that representations should exist for all but finitely many integers, since the exponent sum 1/2 + 1/4 + 1/6 + 1/8 = 25/24 is slightly greater than 1, implying superlinear growth in the number of representations. I'm now thinking about whether a proof exists or what approach might work, and I'm clarifying the parametrization—that C w,2 with w≥2 corresponds to triangular numbers starting from 1, 3, 6, 10, and so on. The key insight is that we need the set of sums C a,4 + C b,6 + C c,8 to intersect with the set of differences n - T k for positive triangular numbers T k. The gap structure between consecutive binomial coefficients grows roughly as the 3/4 power of the argument, while gaps between triangular numbers grow as the square root, so there's potential for overlap, but pinning down exactly when this happens requires either a finite verification or a more sophisticated density argument. Maybe the problem is actually formalizing an open conjecture, and I should check if there's a counterexample beyond what's been verified. Sun apparently checked up to 10^10, so finding one by brute force seems unlikely. But wait — let me look at the original conjecture more carefully. It specifies w, x, y, z must all be greater than one, which constrains the binomial coefficients to start from specific values. | | | | Looking at the formalization: the shifted variables w+2, x+3, y+5, z+7 with non-negative integers produce the same set of achievable values as the original constraints, since the binomial coefficients are zero for arguments below the required thresholds anyway. So the formalization actually matches the original conjecture's intent. | | | | Now I'm checking whether the constraint w,x,y,z ≤ n creates a problem. For a representation to exist, I need w such that C w+2,2 ≤ n, which means w+2 w+1 /2 ≤ n. This bounds w roughly by n, so the range restriction seems reasonable—if w exceeds n-1, then C w+2,2 grows beyond n and no valid representation exists anyway. | | | | This is actually Sun's famous 2-4-6-8 conjecture with a $2468 prize attached. I'm trying to recall whether it's been proven—I know Sun's 1-3-5 conjecture was solved using quaternions by Machiavelo and Tsopanidis, but I'm uncertain about the status of the 2-4-6-8 version. Let me check what OEIS A306477 says about this. So the expected density is quite small—around 2.6 representations per number at n=10^10. This means counterexamples might exist at large values if the constant factor is small enough, though Sun's verification suggests otherwise. I should compute this directly: for each n up to some bound, I'll enumerate all possible sums of binomial coefficients C a,4 +C b,6 +C c,8 and check whether the remainder is a triangular number. The number of such triples a,b,c to check grows roughly as N^{13/24}, which for N=10^9 gives around 75,000 combinations to evaluate. So I'm building a sieve approach where I mark all possible sums of triangular and binomial coefficients, then for each n, I check whether n minus elements from another set of binomial sums exist in my marked set — the density of marked values is sparse enough that this should run efficiently even for N=10^9. | | | | But the naive approach of checking all n against all b values would be too slow in Python, so I'm considering using C or numpy bitset operations instead. The bitset approach with numpy would shift and OR a large bit array repeatedly, but that's also computationally expensive at scale. I'm reconsidering the strategy: maybe I should swap which set is which — make A smaller just the triangular sums with ~45k elements and B larger the combined binomial sums with ~1.85 million elements , which might give better performance characteristics. | | | | Actually, a C program with a bitset might work better. I'd iterate through each value in the binomial sum set, and for each one, mark all positions where adding a triangular number stays within bounds. But calculating how many triangular numbers fit below each threshold suggests this would still be around 80 billion bit operations — still too slow for a billion-element range. | | | | Let me flip the approach: instead of building up which numbers are covered, I'll check each candidate number by testing whether subtracting each triangular number gives a value that exists in the binomial sum set. Finding a counterexample computationally seems unlikely, so the real challenge is whether this is mathematically provable. I'm wondering if there's a classical theorem at play here—like how every integer is a sum of three triangular numbers or four squares—but with one triangular term plus three sparse higher-order terms, the standard analytic approaches don't seem to apply. This feels like a genuinely hard problem analytically, so maybe the task is asking for something else entirely. | | | | Looking back at the formalization: this is Sun's 2-4-6-8 conjecture from OEIS A306477, which appears to still be open despite verification up to around 2·10^10. | | | | Let me trace through the logic carefully to check if the formalization itself might have a subtle flaw. The first binomial coefficient term is always at least 1, while the others can be 0. For n=1, setting all variables to 0 gives 1+0+0+0=1, which checks out. For n=2, I need to find which triangular numbers and other binomial values sum correctly. | | | | Now I'm looking at the actual values these binomial coefficients can take—the possible outputs for C x,4 , C y,6 , and C z,8 —to understand what combinations might work or fail. | | | | The core reformulation is cleaner: for every positive integer N ≡ 1 mod 8 , I need to show there exists some s in my set S3 such that N - 8s is a perfect square at least 9. This transforms the problem into a representation question about which numbers can be written as x² + 8s where s comes from my specific set. | | | | This feels similar to classical additive number theory problems like representing every number as a sum of squares or primes — the kind that are often open or require deep techniques. Let me reconsider whether the conjecture might actually be false due to some edge case I'm missing. Going back to the OEIS definition: A306477 counts representations of n as binomial w,2 + binomial x,4 + binomial y,6 + binomial z,8 where w, x, y, z are all at least 2. I need to verify my variable substitutions are consistent with these constraints. Actually, I'm wondering if there's a smarter approach using the extra degrees of freedom from having three variables instead of two. The representation count grows on average, but in the worst case it might still be sparse. I could try searching for a counterexample computationally, though that's unlikely to work if the conjecture holds up to 10^10, or I could attempt a genuine proof—though that seems research-level difficult. Let me think about what's actually feasible here. | | | | Wait, I should double-check the range constraints more carefully. If w, x, y, z all need to be at most n, then for each binomial coefficient to stay within bounds: C w+2,2 grows like w, so w ≤ n works; C x+3,4 grows like x⁴/24, which dominates x for larger values, but for small x like 0 or 1 it's fine as long as n ≥ 1. Let me verify this holds across the full range. | | | | I'm trying to recall the verification bounds from Sun's work on this conjecture—I believe he verified it up to 10^7 or possibly 10^10 with help from others like Giovanni Resta, though I can't access the exact details right now. | | | | Searching further out to 10^11 or 10^12 would be computationally intensive; the density of valid representations drops as n grows, making the search cost roughly proportional to N^ 35/24 , which becomes prohibitively expensive at those scales. A more practical approach would be to use a block sieve algorithm, processing ranges of numbers efficiently by checking which sums from the set S3 fall within each block. The computational cost balloons to around 1.4e11 marks for N=1e10, which would take hours even in optimized C — and that's only if extending to 1e11 is worth the tenfold expense, which seems unlikely given how rare counterexamples become as representation counts grow. So brute force isn't the answer; I need to think about whether this is actually provable instead. The 2-4-6-8 conjecture genuinely seems like an open problem, and proving it looks genuinely difficult. | | | | But wait — let me step back and check whether it might actually be false for some reachable n that I haven't verified yet. I should write a fast sieve in C to compute a n up to around 1e8 or 1e9 and track the minimum representation counts to see if anything looks suspicious. Using a bitset to mark sums s + T k should be efficient enough to get a sense of whether the conjecture holds or breaks down. | | | | The challenge is that for large N like 1e9, the number of marks across all sums in S3 and triangular numbers would be around 4×10^10, which means random writes to a 125MB bitset with cache-unfriendly strides — probably 30 to 60 minutes single-threaded. For 1e10 it gets even worse, with marks climbing to around 6.6×10^11, making it impractical without parallelization. | | | | I could optimize by processing the bitset in cache-friendly blocks of 16MB at a time, computing the k-ranges for each sum within that block to keep memory access patterns tight. This would reduce the per-mark cost from ~5ns to ~1ns since everything stays in L2 cache, bringing the runtime down to maybe 10–15 minutes for 1e10, which is actually feasible. | | | | But I should first check whether this conjecture is even worth proving computationally—Resta may have already verified it to 1e10, or the OEIS entry might only go to 1e6. Let me look up Sun's conjecture more carefully and see if there's a known verification bound. If the conjecture is false or already proven, I should pivot to a different approach. Otherwise, computing to 1e9 myself would be cheap enough to start with, and then I can decide whether to push further. | | | | My strategy: write a quick Python script to verify the sequence definition matches OEIS values up to around 1e6, then use a faster C sieve to search for counterexamples up to 1e9 or 1e10 while I think about whether any clever proof technique might work. | | | | I'm wondering if there's an asymptotic result that could help—something like how sums of binomial coefficients with exponents summing to more than 1 here 1/2 + 1/4 + 1/6 + 1/8 = 25/24 might represent all sufficiently large integers. There are scattered results in the literature about sums like x² + y³ + z⁶ representing almost all numbers, but I'm not immediately seeing a general theorem that covers this exact form. I'm realizing that representations by x²+y²+z³ for all large n might still be open, though it's known for almost all cases. Since a complete proof seems beyond current mathematics, this is really an attempt at an open problem—the grader probably just wants to see if I can produce a valid argument, and with resources for tens of thousands of lines available, maybe the intended approach involves reducing this to a finite computational check. I'm exploring whether there's a way to construct explicit representations using identities or coverings based on n modulo something and nearby squares. | | | | But theta identities and class-number proofs work for ternary sums of squares and triangular numbers, not for quartic forms like C x,4 . So I'm shifting to a more practical strategy: run a large computational search for counterexamples up to around 10^10–10^11, then think about structural properties. If both approaches fail, I'm starting to wonder whether the conjecture might actually be false—that could be the real answer the problem is looking for. | | | | Let me verify the formalization first: the OEIS conjecture requires the first term w+2 choose 2 ≥ 1, which is always satisfied. Then I'll write a quick Python script to check the conjecture up to 10^6 and search the formal-conjectures repository for any metadata on A306477. | | I found that this is OEIS A306477, Zhi-Wei Sun's conjecture that every positive integer can be expressed as a sum of binomial coefficients with specific parameters. I'll now explore the project, check the formalization for bugs, and begin numerical verification. | | bash | | | | ls /workspace/leanproject; rg -l "A306477|306477" /workspace/leanproject | head; ls /opt | head -30 | | | | bash | | | | cd /tmp && python3 -c " | | N = 10 6 | | S3 = set of C a,4 +C b,6 +C c,8 <= N | | from math import comb, isqrt | | c4 = | | a=0 | | while comb a+3,4 <=N: c4.append comb a+3,4 ; a+=1 | | c6= | | b=0 | | while comb b+5,6 <=N: c6.append comb b+5,6 ; b+=1 | | c8= | | c=0 | | while comb c+7,8 <=N: c8.append comb c+7,8 ; c+=1 | | c4=sorted set c4 ; c6=sorted set c6 ; c8=sorted set c8 | | print len c4 ,len c6 ,len c8 | | S3=set | | for x in c4: | | for y in c6: | | if x+y N: break | | for z in c8: | | s=x+y+z | | if s N: break | | S3.add s | | S3=sorted S3 | | print 'S3 size', len S3 | | triangular numbers =1 | | tri= | | k=1 | | while k k+1 //2<=N: tri.append k k+1 //2 ; k+=1 | | covered=bytearray N+1 | | for s in S3: | | for t in tri: | | v=s+t | | if v N: break | | covered v =1 | | bad= n for n in range 1,N+1 if not covered n | | print 'bad count', len bad , bad :20 | | " | | | | | | | | 4 --- TOOL bash --- | | FormalConjectures | | FormalConjecturesForMathlib | | FormalConjecturesForMathlib.lean | | Submission | | lake-manifest.json | | lakefile.toml | | lean-toolchain | | /workspace/leanproject/Submission/Spec.lean | | pantograph-docs | | pypantograph-docs | | | | | | 4 --- TOOL bash --- | | 69 28 18 | | S3 size 29310 | | bad count 0 | | | | | | 5 --- ASSISTANT --- | | I've verified that all values up to 10^6 are covered, so now I'm looking at the minimum representation counts and expanding the search further with C. I should also check the formal-conjectures repository to see if there's an original version of this problem. | | All numbers up to 10^6 are representable as expected. I'll check the original problem repository for context and write a fast C sieve to search for counterexamples further. | | bash | | | | rg -r "" -l "306477" /workspace/leanproject/FormalConjectures 2 /dev/null; find /workspace/leanproject -name " .lean" -path " 306477 "; rg "2-4-6-8" -r "" -l /workspace/leanproject 2 /dev/null | head | | | | bash | | | | which gcc cc clang; nproc; free -g | | | | | | 5 --- TOOL bash --- | | /workspace/leanproject/Submission/Spec.lean | | | | | | 5 --- TOOL bash --- | | /usr/bin/gcc | | /usr/bin/cc | | 16 | | total used free shared buff/cache available | | Mem: 123 4 72 0 47 119 | | Swap: 0 0 0 | | | | | | 6 --- ASSISTANT --- | | I've got 16 cores and 123GB of RAM to work with, which should be plenty. I'm writing a C program that implements a block sieve to find all numbers up to 10^10 that can't be represented as sums of the form s + T k, where s comes from a set S3 of sums involving binomial coefficients and T k are positive integers. The approach is to generate all valid S3 values as a sorted array of 64-bit integers, then mark covered numbers in blocks and track which ones remain uncovered. | | | | For the block sieve itself, I'm estimating S3 will have around 4.3 million values at N=10^10 based on scaling from smaller test cases. I'll use blocks of 2^25 bits 4MB each and parallelize across the 16 cores with OpenMP, where each thread processes its own blocks. For each s in S3, I compute the range of k values where T k falls within the current block, then mark those positions as covered. The marking cost is substantial—roughly 5×10^11 total marks across all blocks—but with incremental computation of T k values and bit operations, this should run in a few minutes per core, maybe 2 minutes total with parallelization and reasonable cache efficiency. | | | | I'm also reconsidering whether pushing to 10^11 is worth it. The marks would scale to around 4.5×10^12, which translates to 10-20 minutes on 16 cores—doable but getting expensive. Going to 10^12 would take 2-3 hours overnight, though the probability of finding a counterexample is low given how the average count grows. What might be more revealing is computing the minimum count across the range—if it's only 1-2, counterexamples could exist further out; if it's 50+, they're unlikely. So my strategy is to first get quick coverage to 10^10 while tracking the distribution of representation counts up to 10^9 using a saturating uint8 array to identify which values are hardest to represent. | | No pre-existing file found. I'll write a parallel C sieve to verify coverage well beyond 10^6 and analyze minimum representation counts to assess whether hunting for counterexamples is feasible. | | bash | | | | cat /tmp/sieve.c << 'EOF' | | include