Every ordering, from zeros and ones

The statement

Theorem. For every integer N ≥ 1, there are distinct rational numbers s₁, …, sₙ in (−1, 0) with the following property: every permutation of these N indices is the strict increasing order of p(s₁), …, p(sₙ) for some polynomial p with coefficients in {0, 1} and zero constant term.

Each polynomial has only finitely many terms. The same inputs work for all N! permutations, and every comparison is strict. A choice about how to break ties is unnecessary.

It is enough to assign each input a desired rank rᵢ, where the vector of ranks is a permutation of 1, …, N, and arrange that rᵢ < rⱼ implies p(sᵢ) < p(sⱼ).

Try all six orders

For N = 3, fix s₁ = −9/10, s₂ = −4/5 and s₃ = −7/10. These inputs already support all six orders with polynomials of degree at most seven. Select a target order below; the displayed fractions are exact.

For example, p(x) = x⁴ + x⁵ gives values 6561/100000, 8192/100000 and 7203/100000 at the three inputs. The resulting order is p(s₁) < p(s₃) < p(s₂). Across all six certificates, the smallest adjacent gap is 321/50000, which is strictly positive.

1. Interpolate the ranks

Put tᵢ = i/(N + 1) and D = (N − 1)!. For any desired rank vector r, there is an integer polynomial qᵣ of degree at most N − 1 such that qᵣ(tᵢ) = D rᵢ. The factorial makes the interpolation coefficients integral.

Here is the polynomial explicitly: qᵣ(t) = Σᵢ rᵢ (−1)^(N−i) binom(N−1, i−1) ∏ₕ≠ᵢ ((N+1)t − h), where both indices range from 1 to N and the product omits h = i.

All coefficients are integers. At t = tᵢ, every summand except the ith vanishes. In that summand the product is (−1)^(N−i)(i − 1)!(N − i)!, so the signed binomial factor turns it into D. Multiplication by rᵢ gives the required value.

There are finitely many rank vectors. Let C be the largest absolute coefficient among all these polynomials, and let B be the largest sum of absolute coefficients of any one of them. Both are positive integers. We will use one common even integer M = 8NCB for the entire family.

2. Encode each coefficient with distinct powers

Take any q(t) = Σⱼ cⱼtʲ from that family and replace each coefficient cⱼ by |cⱼ| separate monomials. For cⱼ > 0, use powers jM + 2, jM + 4, …, jM + 2cⱼ. For cⱼ < 0, use powers jM + 1, jM + 3, …, jM + 2|cⱼ| − 1. For cⱼ = 0, add nothing. Call the resulting polynomial p.

Every selected exponent is positive, so p has no constant term. Every exponent from the jth coefficient lies in the interval (jM, jM + 2C]. Since M > 2C, these intervals are disjoint. Within each interval the powers are distinct as well. Thus no monomial is repeated, and every coefficient of p is either zero or one.

Now evaluate at s = −t^(1/M). The evenness of M gives s^(jM) = tʲ. Even offsets contribute positively and odd offsets contribute negatively. Each encoded monomial therefore has the intended sign and differs from ±tʲ only by a factor t^α, where 0 < α ≤ 2C/M.

3. Keep the error below a rank gap

For α > 0 and 0 < t ≤ 1, convexity of u ↦ u^(−α), applied at u = 1, gives 0 ≤ 1 − t^α ≤ α(t⁻¹ − 1). At our interpolation inputs, t ≥ 1/(N + 1), so t⁻¹ − 1 ≤ N.

Consequently each encoded monomial differs from its intended contribution by at most 2CN/M: its extra factor has that error bound, and tʲ ≤ 1. There are at most B monomials, so |p(−t^(1/M)) − q(t)| ≤ 2CNB/M = 1/4.

Fix sᵢ = −tᵢ^(1/M). Apply the encoding to every qᵣ. Each value pᵣ(sᵢ) is within 1/4 of D rᵢ. If rᵢ < rⱼ, subtraction gives pᵣ(sⱼ) − pᵣ(sᵢ) ≥ D − 1/2 > 0. Thus the same N negative inputs realize every ordering.

These inputs may be irrational. However, we have only finitely many polynomials and finitely many strict inequalities. Continuity preserves all of them under sufficiently small perturbations of the inputs. Choose disjoint neighborhoods inside (−1, 0) and a rational number in each. The resulting distinct rational inputs satisfy all the same inequalities. This proves the theorem, including N = 1.

An explicit bound, with room to improve

The maximum over interpolation polynomials is finite, but a direct bound avoids enumerating them. Put H = N(4N + 2)^(N−1) and choose the even integer M = 8NH². Then sᵢ = −(i/(N + 1))^(1/M) gives one explicit set of real inputs that works.

Indeed, the sum of absolute coefficients in the ith interpolation basis polynomial is at most binom(N − 1, i − 1)(2N + 1)^(N−1). Multiply by rᵢ ≤ N and sum over i to obtain B ≤ H, hence also C ≤ H. The same error estimate is at most 1/4.

The encoded polynomials have degree at most (N − 1)M + 2H. This is a sufficient existence bound. It is large, and no optimality is claimed. A natural next question is how small the maximum degree can be when the inputs are chosen well.

What was checked, and who did the work

The constructive verifier checked all 873 rank vectors for N = 1 through 6, including exact integer interpolation, exponent separation, signs and the uniform error bound. High precision evaluations were supplementary diagnostics. A separately written program checked all target permutations for N ≤ 4 using exact rational enclosing intervals, without floating point evaluations of the algebraic inputs.

The compact three-input example above and a four-input example covering all 24 orderings were independently rechecked using rational arithmetic. The four-input certificates have degree at most 16; every witness and exact value is in the downloadable code bundle. These checks support the implementations and examples; the argument for arbitrary N is the proof above.

Sulayman Bowles initiated and directed the research. OpenAI Codex found the requests, developed the mathematical arguments, drafted this article and the accompanying note, and wrote and ran the verification code. Separately prompted Codex instances reviewed the proofs and wrote independent exact checks. This is automated review, without external peer review or formal proof-assistant verification. The affirmative answer addresses ABB’s stated question; historical priority has not been established.

A second requested proof

A separate April 2025 request asks why a double-binomial recurrence produces OEIS A302285, whose generating function is the continued fraction 1/(1 − x − x/(1 − 2x − x/(1 − 3x − …))). The accompanying note gives a proof of that identity. The request. The sequence.

The useful step is to introduce polynomial coefficients Pₙ(t) of formal tails Fₕ = t/(1 − (h+1)x − xFₕ₊₁). Differentiating the tail identity yields P₀ = t and Pₙ = tP′ₙ₋₁ + Σᵢ₌₀ⁿ⁻¹ Pₙ₋ᵢ₋₁Pᵢ. Applying the kth power of the derivation t d/dt and evaluating at t = 1 gives the exact binomial Leibniz rule required by the question’s recurrence. At k = 0, it gives the continued-fraction sequence.

Independent exact checks agreed on 2,556 recurrence pairs with n + k ≤ 70. The full formal-series argument and executable checks are in the downloads. Alexander Burstein’s comment on the question provides the colored Schröder-path interpretation; the surrounding T-fraction theory is prior work of Bitonti, Deb and Sokal, whose Table 1 includes A302285. No new general theory of continued fractions is claimed. Prior research.

Sources

1. ABB — On the coverage of permutations by argsort of polynomial evaluations

   MathOverflow · 2025-04-08 · Original mathematical request

   Verified Oct 19, 2026

   The question asks for one fixed tuple of distinct real inputs on which zero-constant polynomials with coefficients in {0,1} realize every permutation. The individual page and direct Stack Exchange answer endpoint displayed no answers when inspected.

2. user231922 — Recursion for A302285

   MathOverflow · 2025-04-10 · Original mathematical request

   Verified Oct 19, 2026

   Contains the double-binomial recurrence. Alexander Burstein’s comment gives prior combinatorial context.

3. A302285 — The On-Line Encyclopedia of Integer Sequences

   The OEIS Foundation Inc. · Sequence and prior references

   Verified Oct 19, 2026

   The continued fraction, displayed terms and cited combinatorics predate this note.

4. Bitonti, Deb and Sokal — Thron-type continued fractions for some classes of increasing trees

   arXiv · 2024-12-13 · Prior research, version 1

   Verified Oct 19, 2026

   Table 1 on page 58 includes A302285; cited as prior continued-fraction context.

Supporting material

• Solutions to two requested mathematical problems

  Five-page note with both complete proofs, examples, verification results and the Codex disclosure. This retained pre-publication PDF records that no external answer had been posted when it was written.

• Proofs, source and exact verification programs

  LaTeX source, standard-library Python programs, rational certificates and independent automated review reports. Includes a README with commands for reproducing the checks.

Read next