Independent adversarial review — MathOverflow 490705

Verdict: the proposed all-N construction is correct. No gap found.

1. At t_i=i/(N+1), the Lagrange basis polynomial is
   prod_{h!=i}((N+1)t-h) / [(-1)^(N-i)(i-1)!(N-i)!].
   Multiplying it by D=(N-1)! gives integer coefficients.
   Thus q_r(t_i)=D*r_i can be interpolated over Z for every rank vector r.

2. The finite family of interpolants has positive integer bounds C and B,
   where C bounds individual coefficient magnitudes and B bounds each l1 norm.
   The definition also works at N=1: q=1, C=B=1, M=8.

3. M=8NCB is even and exceeds 2C. The nodes
   s_i=-(i/(N+1))^(1/M) are real, distinct and in (-1,0).
   For e=jM+r, s_i^e=(-1)^r*t_i^(j+r/M).
   Positive coefficient c_j is encoded by even r=2,4,...,2c_j;
   negative coefficient is encoded by odd r=1,3,...,2|c_j|-1.
   Since 1<=r<=2C<M, all exponents are positive and disjoint across j.
   Every resulting polynomial therefore has coefficients 0 or 1 and zero
   constant term, including the block that approximates q's constant term.

4. No logarithm is needed in the error estimate. Convexity of x->x^(-alpha)
   gives 0<=1-t^alpha<=alpha*(1/t-1)<=N*alpha for alpha>=0 and
   1/(N+1)<=t<1. Summing yields absolute error <=2CNB/M=1/4.
   Hence target gaps D>=1 leave actual gaps >=D-1/2>0.

5. The source defines l as a vector of ranks, notwithstanding the word
   argsort. The construction directly realizes every rank vector, and also
   covers all permutations under the inverse convention.

Independent exact code: independent_verify.py
Exact arithmetic certificate: exact_audit.json
All target rankings for N=1,2,3,4 passed.
No floating-point or approximate root evaluations are used.

Optional compact N=3 example:
D=2, C=52, B=116; q coefficients by target ranks:
(1,2,3): [0,8,0]
(1,3,2): [-8,52,-48]
(2,1,3): [12,-44,48]
(2,3,1): [-4,44,-48]
(3,1,2): [16,-52,48]
(3,2,1): [8,-8,0]
The general theorem chooses M=144768. Exact one-sided error estimates also
show M=974 works for this N=3 family, with maximum actual degree 2044 and
minimum certified adjacent evaluation gap 3/974.

This establishes mathematical correctness of the direct answer. It is not
an assertion of historical priority, formal proof-assistant verification,
or journal suitability.
