CS Paper Radar

Proofs of some OEIS conjectures on Wythoff sums, Fibonacci and Lucas words

Alex Ashburn

cs.FL math.NTmath.CO ·submitted 2026-10-04 00:55 UTC · v1
theory

Abstract

We prove several conjectures from the On-Line Encyclopedia of Integer Sequences about the lower and upper Wythoff sequences and the Fibonacci word. Among them are two of Kimberling's three conjectures on the number of ways to write $n=\lfloor h\varphi\rfloor+\lfloor k\varphi^2\rfloor$ with $h,k\ge1$ (A259598): exactly one way if and only if $n+1=2F$ for a Fibonacci number $F\ge2$, and exactly two ways if and only if $n+1\ge7$ is a Lucas number. The third conjecture, that no way exists if and only if $n+1$ is a Fibonacci number, was proved earlier by Kawsumarng et al. We also observe that Kimberling's conjecture on the gaps of the sums of two distinct terms of A003622 and of their complement (A333308, A333309) follows, after a shift by $2$, from earlier Walnut results of Shallit and of Bosma et al. on A260317, and we re-verify it. Next, we prove Kimberling's five 2025 conjectures on the gaps between positions where the Fibonacci word and the "Lucas word" take prescribed values (A383423-A383427). Finally, we prove a conjecture of Mathar on A285383, and we point out that a conjecture of Schmidt on A003250 follows from theorems of Carlitz, Scoville and Vaughan (1973); we also confirm it with Walnut. Most proofs are decision procedures run in the free prover Walnut, and we supply the complete command file.

Comment
5 pages; the complete Walnut command file is an ancillary file. Also deposited at Zenodo, doi:10.5281/zenodo.23124896

Closest papers

Nearest neighbours by meaning across the whole index.

Re-Ordering the Generalized Hofstadter Functions G, H, and Beyond

cs.DM cs.FLmath.NT ·2026-10-26 ·Pierre Letouzey
theory similarity 0.60
Abstract

Hofstadter's G function is recursively defined via G(0) = 0 and then G(n) = n-G(G(n -1)). Following Hofstadter, we vary the number k of nested recursive calls in this equation and obtain a family of functions (F\_k). In a previous article, we proved that this family is ordered pointwise: for all k and n, we have $F_k(n) $le$ F_{k+1}(n)$. Here we propose a much shorter proof of this theorem, without infinite morphic words. The key ingredient for this direct proof is a new formula expressing iterates of the preimages of $F_k$ . Thanks to this formula, we also prove several conjectures mentioned in our previous article. In particular we obtain that $F_k(n) < F_{k+1}(n)$ when n > (k + 1)(k + 6)/2. We provide a certified formalization of all these results in the Rocq proof assistant.

0.25

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.57
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Three Quadratic Recurrences Modulo 3: What We Can Prove and What We Can Guess

cs.DM math.NTmath.CO ·2026-10-25 ·Steven Finch
similarity 0.56
Abstract · 10 pages

We study three innocent-looking recurrences modulo $3$, each built from squares of two earlier terms. One of them turns out to be secretly $\textit{linear}$, and we can compute its periods exactly. One is a $\textit{permutation}$ hiding a small, perfectly orderly piece inside a large, random-looking one. The third looks thoroughly random, but it still has a few provable features. Along the way we meet open problems that need nothing beyond a first course in abstract algebra to state. This paper is a starting point, not the final word in any sense.

0.31

An Improved Lower Bound for Separating Words by Permutation Automata

cs.FL ·2026-10-08 ·Chen Xu, Kenneth Regan
theoryhot direction similarity 0.55
Abstract

We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $Ω(\log n\log\log n)$ states to separate by a deterministic finite automaton whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity of $\mathfrak{S}_k$ of length $\exp(O(k/\log k))$. This improves the previous lower bound $(3/2-o(1))\log n$ of Bulatov, Karpova, Shur, and Startsev (arXiv:1609.03199). The proof combines a positive-word construction with a cover of permutation orders. Consecutive segments of prime powers reduce the covering problem to enumerating sets of positive integers with bounded sum. The required estimates use the central binomial coefficient and the classical asymptotic formula for partitions into distinct parts. An appendix gives sharper constants and lower-order terms using a greedy cover and a quantitative prime number theorem.

0.28

A new lower bound for the sixth Schur number: $S(6)\ge 537$

cs.DM math.CO ·2026-10-22 ·Zhiyang Chen, Ligeng Zhu, Fan Long
theory similarity 0.54
Abstract

We give an explicit partition of $\{1,\ldots,537\}$ into six sum-free sets, establishing $S(6)\ge 537$. This improves the lower bound 536 of Fredricksen and Sweet (2000). Known recursive constructions then give the improved lower bounds $S(8)\ge 5\,372$, $S(11)\ge 204\,208$, $S(13)\ge 2\,042\,082$, and $R_6(3)\ge 539$. We also report 131 pairwise inequivalent partitions found by the search. We describe their structure and provide the complete partitions in the supplementary material. These partitions provide starting points for future searches and structural studies of Schur partitions.

0.27

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.54
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.53
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

Double circulant LCD codes over $\mathbb{F}_2+u\mathbb{F}_2$ and their related binary LCD codes

cs.IT math.RA ·2026-10-12 ·Xingxing Xu, Bo Wu, Jon-Lark Kim
theory similarity 0.53
Abstract

Linear complementary dual (LCD) codes are linear codes that intersect their dual trivially. We study double circulant (Euclidean) LCD codes over the finite chain ring $R=\mathbb F_2+u\mathbb F_2$, where $u^2=0$. Using the Chinese Remainder Theorem and the factorization of $x^n-1$, we derive an explicit enumeration formula, with a separate treatment of the constituent corresponding to $x-1$, which is not obtained by a formal specialization of the previously known counting formula over $\mathbb F_q[u]/(u^k)$. Assuming Artin's primitive root conjecture for $2$, we show that the binary Gray images contain an asymptotically good family of rate $1/2$ which attains the asymptotic Gilbert--Varshamov bound, i.e., whose relative distance can approach $H_2^{-1}(1/2)$ from below. More importantly from the constructive viewpoint, by combining Gray images with a known extension construction, we obtain a binary LCD code with previously unknown parameters $[29,15,7]$ and construct two explicit permutation-inequivalent binary LCD codes with parameters $[45,23,9]$ and nine binary LCD codes with the best known parameters.

0.25