Random permutations of quadratic length contain every pattern
Alon’s 1000n² problem solved, ‘the proof was found by GPT-6 Pro’ (Chen, Wang)
Event confirmedAwaiting review
The takeaway
The authors of this combinatorics paper state in the abstract that the model found the proof and that they ‘do not claim credit for the proof ideas’. It settles the order of magnitude in a problem posed by Noga Alon.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 12 October 2026
Your AI and this story
- GPT-6 Astra162 days after its cutoff
- Claude Opus 5.5101 days after its cutoff
- Gemini 3.8 Flash192 days after its cutoff
- Grok 4.7131 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 101 days before it.
Key facts
- Paper: ‘Quadratic-size Random Permutations are Universal’, arXiv 2610.13530 [math.CO], 9 Oct 2026; Yu Chen (Beijing Institute of Technology) and Yiting Wang (supported by the ERC grant RANDSTRUCT)
- Theorem 1.1: there are absolute constants c > 0 and n₀ such that for n ≥ n₀ a uniformly random permutation of length 32n² fails to be n-universal with probability at most exp(−cn/log n)
- Background (paper): Alon conjectured that length (1 + ε)n²/4 suffices, observed that O(n² log n) does, ‘and posed the weaker problem of proving that 1000n² suffices’; He and Kwan proved 2000n² log log n. Length below about n²/4 cannot work, because of the longest increasing subsequence
- What remains open (paper): ‘the sharp constant 1/4 predicted by Alon’s conjecture remains open’; the authors sketch how to lower 32 to any constant above 1 and why 1 is a barrier for the method
- Declaration on the usage of generative AI: ‘The proof was found by GPT-6 Pro. The authors do not claim credit for the proof ideas. They have verified and digested the proof and take full responsibility for the correctness of the manuscript.’
- Not found as of 12 Oct 2026: reactions from Alon, He or Kwan, or other expert comment
What happened
A permutation is n-universal if every ordering of n items appears inside it as a pattern. Any universal permutation needs length of order n², and Noga Alon asked whether a random permutation of length a constant times n² is already universal. Xiaoyu He and Matthew Kwan came within a log log n factor. Chen and Wang’s paper removes that factor, so the order of magnitude is now known.
The authors state plainly that the model did the mathematics: GPT-6 Pro found the proof, and their own contribution was to verify, digest and write it. The prompt and the time taken are not given.
Why it matters
It is a clean case of a model resolving a problem that specialists had posed and partly solved, with authors who attribute the ideas to the model in the abstract. The problem is of interest to specialists more than a famous conjecture, and the result is not sharp.
What is disputed or not yet verified
| Verification | Unrefereed preprint; proof checked by the authors |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed from the arXiv PDF