Exact discrepancy of letter positions in fixed points of binary morphisms, with an application to conjectures of Kimberling

Abstract

In 2017 Kimberling added to the On-Line Encyclopedia of Integer Sequences a large family of conjectures of the form L < nr − a(n) < U for all n ≥ 1. Here a(n) is the position of the n-th 0 (or 1) in the fixed point, or limiting word, of a morphism on {0,1}, and 1/r is the frequency of that letter. Using the Dumont–Thomas numeration we show that, when the second eigenvalue λ₂ of the incidence matrix satisfies |λ₂| < 1, the exact supremum and infimum of nr − a(n) are affine functions of the unique solution of a four-variable max–min linear system over Q(√d). The solution comes with an exact certificate. We compute the exact supremum and infimum for all 78 position sequences in this family. Sixty of the conjectures hold (four of them after correcting an evident misprint). Fifteen of these were proved before or follow by short arguments from published results, and three more follow from a published theorem whose printed proof contains a numerical slip; for the other 42 we found no earlier proof. Eighteen conjectures fail. Most failures occur at very small n, but the conjectured bounds for A284365 and A284366 first fail at n = 8 933 313 and n = 2 977 771. The optimal bounds are −(12 + 2√21)/15 and (6 + √21)/5 for A284365, and (√21 − 9)/5 and (6 + √21)/5 for A284366. For four sequences with |λ₂| > 1 the discrepancy is unbounded on one side, and we determine the other side. We also determine the exact ranges for six older entries defined by other recursions (A026363, A026364, A026367, A026368, A045671, A045672), after showing that they are position sequences of such fixed points; this confirms Kimberling's conjectures for them (two also follow from theorems of Shallit, and two from the statement of a theorem of Fokkink and Joshi). We supply the certificates and an independent checker. Version 2: a new section compares the results with earlier work. The conjectures for 15 sequences were proved before or follow from results of Dekking, Shallit, and Fokkink and Joshi, or from the Sturmian structure of two of the words, and three more follow from the statement of a theorem of Fokkink and Joshi whose printed proof contains a numerical slip; version 1 wrongly said that 57 of the true conjectures had not been proved before. We thank a reviewer of version 1 for pointing out that the conjectures for A284773 and A284774 follow from theorems of Shallit. The results table (Section 6) now marks these cases, credits in Sections 1, 4 and 7 were revised, two references were added (Coons, Ramsey and Strungaru; Lothaire), and the text field known in the certificate files now records the earlier results. The supplementary checker now compares the exact infimum and supremum with the recorded values, checks the infinite sides and the counterexamples more strictly, and exits with a nonzero status on any failure; a test script with deliberately corrupted certificates and a numerical check of the identities in the new section are added. No computed value and no result changed.