HEXAGONbeta

The minimum number of distinct abelian squares in a binary circular word

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricscs.DM — Discrete Mathematicscs.FL — Formal Languages and Automata Theory

Contributed by Deep Bhattacharjee

Version 2 / Oct 22, 2026 / CC BY 4.0

Abstract

We prove that every binary circular word of length nn contains at least $\fl{(n-1)/2}$ distinct abelian squares, and we determine all words attaining this bound. This settles a conjecture of Simpson: its odd case holds, and in its even case the list of extremal words misses (ab)n/2(ab)^{n/2} for n≡2(mod4)n\equiv 2\pmod 4, n≥6n\ge 6. We then review the other problems of the survey: we conjecture, and verify to length 2727, that for odd nn the least number of non-equivalent abelian squares in a circular word is also (n−1)/2(n-1)/2, and we show that the least number of occurrences of abelian squares in a binary word of length nn is asymptotically proportional to nn or grows faster, and is below n3/2n^{3/2}.

Provenance statement

Tools used: Claude Fable 5.1 Medium with Lean 4 with Mathlib (formalisation of Theorem 1.1); C, C++, Python, Julia and shell programs (checks); LaTeX (amsart, single column). arXiv identifier: none (not posted on arXiv). Code: https://github.com/creelie/literate-octo-lamp, release v2.3.0, version DOI 10.5281/zenodo.23692500 (all versions: https://doi.org/10.5281/zenodo.23313258).
AI provenance filesAI_PROVENANCE.md · 3 KB

Tools used

Anthropic
Claude CodeVersion Fable 5.1 Medium

References

  1. J. Simpson, Solved and unsolved problems about abelian squares, preprint (2018), arXiv:1802.04481v1 (https://arxiv.org/abs/1802.04481v1).arXiv
  2. A.\,S. Fraenkel, J. Simpson, M. Paterson, On weak circular squares in binary words, in: Combinatorial Pattern Matching (CPM 1997), Lecture Notes in Computer Science, Springer, 1997, pp. 76--82, doi:10.1007/3-540-63220-4_51 (https://doi.org/10.1007/3-540-63220-4_51).DOI
  3. S.\,Z. Fazekas, A. Mammoliti, R. Mercaş, J. Simpson, Binary words containing few abelian squares, preprint (2026), arXiv:2604.23188v1 (https://arxiv.org/abs/2604.23188v1).arXiv
  4. G. Fici, F. Mignosi, Words with the maximum number of abelian squares, in: Combinatorics on Words (WORDS 2015), Lecture Notes in Computer Science, Springer, 2015, pp. 122--134, doi:10.1007/978-3-319-23660-5_11 (https://doi.org/10.1007/978-3-319-23660-5_11).DOI
  5. G. Fici, F. Mignosi, J. Shallit, Abelian-square-rich words, Theoret. Comput. Sci. 684 (2017) 29--42, doi:10.1016/j.tcs.2017.02.012 (https://doi.org/10.1016/j.tcs.2017.02.012).DOI
  6. G. Fici, S. Puzynina, Abelian combinatorics on words: a survey, Comput. Sci. Rev. 47 (2023) 100532, doi:10.1016/j.cosrev.2022.100532 (https://doi.org/10.1016/j.cosrev.2022.100532).DOI
  7. L. de Moura, S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction -- CADE 28, Lecture Notes in Computer Science, Springer, 2021, pp. 625--635, doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
  8. The mathlib Community, The Lean mathematical library, in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, pp. 367--381, doi:10.1145/3372885.3373824 (https://doi.org/10.1145/3372885.3373824).DOI
  9. S. Triki, Abelian-square factors and binary words, preprint (2019), arXiv:1907.05369v1 (https://arxiv.org/abs/1907.05369v1).arXiv
  10. T. Kociumaka, J. Radoszewski, W. Rytter, T. Waleń, Maximum number of distinct and nonequivalent nonstandard squares in a word, Theoret. Comput. Sci. 648 (2016) 84--95, doi:10.1016/j.tcs.2016.08.010 (https://doi.org/10.1016/j.tcs.2016.08.010).DOI
Show all 12 referencesShow fewer references
  1. M. Rao, M. Rosenfeld, Avoidability of long kk-abelian repetitions, Math. Comp. 85 (2016) 3051--3060, doi:10.1090/mcom/3085 (https://doi.org/10.1090/mcom/3085).DOI
  2. OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, sequence A268084, https://oeis.org/A268084, accessed 27 October 2026.link

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositSupersededOct 22, 2026
  2. v2Submitted by Deep BhattacharjeeSubmitted as a new versionCurrentOct 27, 2026