Every ordering, from zeros and ones

The statement

Theorem. For every integer N ≥ 1, there are distinct rational numbers $s_1$, …, $s_n$ in (−1, 0) with the following property: every permutation of these N indices is the strict increasing order of p($s_1$), …, p($s_n$) 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_i$, where the vector of ranks is a permutation of 1, …, N, and arrange that $r_i$ < $r_j$ implies p($s_i$) < p($s_j$).

All six orders on the same three inputs

For N = 3, fix $s_1$ = −9/10, $s_2$ = −4/5 and $s_3$ = −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^4$ + $x^5$ gives values 6561/100000, 8192/100000 and 7203/100000 at the three inputs. The resulting order is p($s_1$) < p($s_3$) < p($s_2$). Across all six certificates, the smallest adjacent gap is 321/50000, which is strictly positive.

1. Interpolation assigns the ranks

Integer interpolation gives each coefficient a form the encoding can use: its magnitude becomes a count of monomials, and its sign determines whether their exponents are even or odd. First assign the desired ranks in that more flexible language. Then translate the whole finite family into binary polynomials without losing the gaps between ranks.

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

Here is the polynomial explicitly: $$q_r\left(t\right)=\sum _i{r}_i{\left(-1\right)}^{N-i}\left(\genfrac{}{}{0ex}{}{N-1}{i-1}\right)\prod _{h\ne i}\left(\left(N+1\right)t-h\right)\text{,}$$Scroll formula → where both indices range from 1 to N and the product omits h = i.

All coefficients are integers. At t = $t_i$, every summand except the ith vanishes. In that summand the product is ${\left(-1\right)}^{N-i}$(i − 1)!(N − i)!, so the signed binomial factor turns it into D. Multiplication by $r_i$ 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. Bounding the whole family at once lets us use one common even integer M = 8NCB.

2. Encoding each coefficient with powers

Take any q(t) = $\sum _j$ $c_j$$t^j$ from that family and replace each coefficient $c_j$ by |$c_j$| individual monomials. For $c_j$ > 0, use powers jM + 2, jM + 4, …, jM + 2$c_j$. For $c_j$ < 0, use powers jM + 1, jM + 3, …, jM + 2|$c_j$| − 1. For $c_j$ = 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 different 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^j$. Even offsets contribute positively and odd offsets contribute negatively. Each encoded monomial therefore has the intended sign and differs from ±$t^j$ only by a factor $t^{\alpha }$, where 0 < α ≤ 2C/M.

3. The error stays below the rank gap

For α > 0 and 0 < t ≤ 1, convexity of u ↦ $u^{-\alpha }$, applied at u = 1, gives $0\le 1-t^{\alpha }\le \alpha \left(t^{-1}-1\right)$. At our interpolation inputs, t ≥ 1/(N + 1), so $t^{-1}$ − 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^j$ ≤ 1. There are at most B monomials, so $$\begin{array}{l}|p\left(-t^{1/M}\right)-q\left(t\right)|\le 2CNB/M\\ =1/4\text{.}\end{array}$$Scroll formula →

Fix $s_i$ = −$t_i^{1/M}$. Apply the encoding to every $q_r$. Each value $p_r$($s_i$) is within 1/4 of D $r_i$. If $r_i$ < $r_j$, subtraction gives $p_r\left(s_j\right)-p_r\left(s_i\right)\ge D-1/2>0$. Thus the same N negative inputs realize every ordering.

The construction so far gives real inputs that may be irrational. To obtain rational inputs, use the fact that 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 rational inputs, still all different, satisfy all the same inequalities. This proves the theorem, including N = 1.

Strictness is doing the work in the rational-input step. The finite family leaves a positive margin that survives a sufficiently small common perturbation. This establishes rational inputs without optimizing their denominators or the degree of their certificates. Those efficiency questions remain visible in the gap between the large general bound and the compact examples.

An explicit bound, with room to improve

The maximum over interpolation polynomials is finite, but a direct bound avoids enumerating them. Put H = N${\left(4N+2\right)}^{N-1}$ and choose the even integer M = 8N$H^2$. Then $s_i$ = −${\left(i/\left(N+1\right)\right)}^{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 $\left(\genfrac{}{}{0ex}{}{N-1}{i-1}\right)$${\left(2N+1\right)}^{N-1}$. Multiply by $r_i$ ≤ 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 large sufficient bound proves existence while leaving room to reduce the degree. The next question is how small the maximum degree can be when the inputs are chosen well.

An alternative research direction would start with rational inputs with generous gaps and try to reduce the degree directly, instead of encoding a whole interpolation family with a common large spacing. It would have to protect the smallest comparison gap, not just reproduce most permutations numerically. A lower degree bought by unstable near-ties would answer a weaker practical question.

Exact checks cover the examples and implementations

The constructive verifier checked all 873 rank vectors for N = 1 through 6, including exact integer interpolation, nonoverlapping exponents, 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.

The divisibility-witness argument proves existence and then tracks the size of an explicit witness. Each claim needs its own proof.

A continued-fraction note

The other requested problem now has its own proof note. It derives the double-binomial recurrence from formal tails and links the exact checks and prior T-fraction work.

One fixed tuple of rational inputs suffices for every strict ordering; changing the binary polynomial does all the work. The price of this general construction is its degree, so a smaller certificate would improve its efficiency without changing the existence result.