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.
Minjia Shi, Xuan Wang, Bouazzaoui Zakariae, Jon-Lark Kim, Patrick Solé
原文摘要
Wall-Sun-Sun primes (shortly WSS primes) are defined as those primes $p$ such that the period of the Fibonacci recurrence is the same modulo $p$ and modulo $p^2.$ This concept has been generalized recently to certain second order recurrences whose characteristic polynomials admit as a zero the principal unit of $\mathbb{Q}(\sqrt{d}),$ for some integer $d>0.$ Primes of the latter type we call $WSS(d).$ They correspond to the case when $\mathbb{Q}(\sqrt{d})$ is not $p$-rational. For such a prime $p$ we study the weight distributions of the cyclic codes over $\mathbb{F}_p$ and $\mathbb{Z}_{p^2}$ whose check polynomial is the reciprocal of the said characteristic polynomial. Some of these codes are MDS (reducible case) or NMDS (irreducible case).
Tony Feng, Trieu Trinh, Garrett Bingham, Jiwon Kang, Shengtong Zhang, Sang-hyun Kim, Kevin Barreto, Carl Schildkraut 等 24 位作者
原文摘要
We present a case study in semi-autonomous mathematics discovery, using Gemini to systematically evaluate 700 conjectures labeled 'Open' in Bloom's Erdős Problems database. We employ a hybrid methodology: AI-driven natural language verification to narrow the search space, followed by human expert evaluation to gauge correctness and novelty. We address 13 problems that were marked 'Open' in the database: 5 through seemingly novel autonomous solutions, and 8 through identification of previous solutions in the existing literature. Our findings suggest that the 'Open' status of the problems was through obscurity rather than difficulty. We also identify and discuss issues arising in applying AI to math conjectures at scale, highlighting the difficulty of literature identification and the risk of ''subconscious plagiarism'' by AI. We reflect on the takeaways from AI-assisted efforts on the Erdős Problems.