Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Composing the three consecutive-gap bounds


Let A\mathcal A be all circle sequences and D⊂A\mathcal D\subset\mathcal A those with distinct terms. Both are nonempty. Use the cyclic labels, real lifts and extrema defined in L165. For n≥rn\ge r, each cyclic gap occurs in exactly rr spans, so

0≤nmn(r)≤r≤nMn(r).0\le nm_n^{(r)}\le r\le nM_n^{(r)}.

This also gives Mn(r)>0M_n^{(r)}>0, making the extended ratio convention unambiguous. All following limits ignore the finite prefix n<rn<r.

L163 gives an absolute threshold rRr_R and, for every r≥rRr\ge r_R and every X∈AX\in\mathcal A, the ratio lower bound with coefficient 1/2001/200. L164 gives absolute c>0,rOc>0,r_O and the two separate deviation lower bounds for every r≥rOr\ge r_O and every X∈AX\in\mathcal A. Both use circumference one, ordering by position with index breaking ties, the lifts yi+n=yi+1y_{i+n}=y_i+1, rr consecutive gaps, multiplicity, integer n≥rn\ge r, and natural logs. The ratio convention is M/0=+∞M/0=+\infty; the one-sided proof divides by no minimum. Set r0=max⁡(rR,rO)r_0=\max(r_R,r_O). Then all three assertions hold for every fixed r≥r0r\ge r_0 and every sequence. Their limsups need not be witnessed by the same subsequence.

For any such rr, put a=clog⁡ra=c\sqrt{\log r} and b=log⁡r/200b=\log r/200. The universal upper-span deviation bound gives lim sup⁡nnMn(r)≥r+a\limsup_n nM_n^{(r)}\ge r+a for every sequence. Taking its infimum over A\mathcal A gives ΛrA−r≥a\Lambda_r^{\mathcal A}-r\ge a. Since the scaled minima are in [0,r][0,r],

lim sup⁡n(r−nmn(r))=r−lim inf⁡nnmn(r).\limsup_n(r-nm_n^{(r)})=r-\liminf_n nm_n^{(r)}.

The lower-deviation bound therefore gives lim inf⁡nnmn(r)≤r−a\liminf_n nm_n^{(r)}\le r-a for each sequence. Taking the supremum proves r−λrA≥ar-\lambda_r^{\mathcal A}\ge a. Taking the infimum of the actual sequence limsup ratios gives μrA≥1+b/r\mu_r^{\mathcal A}\ge1+b/r, hence r(μrA−1)≥br(\mu_r^{\mathcal A}-1)\ge b. None of these operations exchanges a limit with an infimum or supremum, requires attainment, or combines separately optimized numerator and denominator.

For the subclass, order alone gives

ΛrD≥ΛrA,λrD≤λrA,μrD≥μrA.\Lambda_r^{\mathcal D}\ge\Lambda_r^{\mathcal A},\qquad \lambda_r^{\mathcal D}\le\lambda_r^{\mathcal A},\qquad \mu_r^{\mathcal D}\ge\mu_r^{\mathcal A}.

Thus the same three lower bounds hold for D\mathcal D. Equality between these extrema is not needed. As rr tends through the positive integers, both aa and bb tend to infinity, proving each claimed divergence.

In the modified Statement of Problem 1221, the extrema range over A\mathcal A. The displayed maximum and minimum mean the extrema over the nn cyclic starting labels, and its distance is the forward arc through rr consecutive gaps, as its Notes specify. These are exactly the definitions used above. Its three requested expressions are exactly the three just bounded. The printed first two expressions r(Λr−1)r(\Lambda_r-1) and r(1−λr)r(1-\lambda_r) are different quantities; no conclusion about them is substituted for the modified Statement. Their historical interpretation is outside this proof.