论文标题
长度n的词不到1.5n不同的正方形的证明
A proof that a word of length n has less than 1.5n distinct squares
论文作者
论文摘要
我们对单词中最大数量的不同正方形感兴趣。 Fraenkel和Simpson引入了这个问题，他们以长度为n的单词提出了2N的界限，并认为该界限小于n。由于问题是在重复上，因此他们的解决方案依赖于Fine和Wilf的周期性引理。然后，Ilie完善了他们的结果，并提出了2N-O（log n）的界限。 Lam使用诱导来获得95N/48的界限。 Deza，Franek和Thierry通过组合方法实现了11N/6的界限。使用蒂埃里（Thierry）提出的中断核心的特性，我们在这里完善了Deza，Franek和Thierry所展示的组合结构，以提供3N/2的结合。
We are interested in the maximal number of distinct squares in a word. This problem was introduced by Fraenkel and Simpson, who presented a bound of 2n for a word of length n, and conjectured that the bound was less than n. Being that the problem is on repetitions, their solution relies on Fine and Wilf's Periodicity lemma. Ilie then refined their result and presented a bound of 2n-O(log n). Lam used an induction to get a bound of 95n/48. Deza, Franek and Thierry achieved a bound of 11n/6 through a combinatorial approach. Using the properties of the core of the interrupt, presented by Thierry, we refined here the combinatorial structures exhibited by Deza, Franek and Thierry to offer a bound of 3n/2.
