Thue-Morse序列在加法表示数相等问题中的唯一性结构探究

《Discrete Applied Mathematics》：On the integer sets with identical representation functions

这篇综述深入探讨了基于Thue-Morse序列的加法表示数（RS(n)）相等问题。作者系统回顾了该领域的关键进展，特别是针对有限区间[0, m]上，两个集合C和D在给定特定并集与交集结构（例如C∪D=[0, m]{r1}, C∩D={r2}）下，其所有非负整数n的表示数RC(n)=RD(n)成立的充分必要条件。文章最终在定理1.1中给出了此类结构完全由Thue-Morse序列及其变体决定的完整刻画，为这一组合数论中的经典问题提供了重要的结构性结论。

　　

Highlights

• •
  本文研究了非负整数子集C和D的加法表示数R_C(n)和R_D(n)对所有非负整数n均相等的条件。
• •
  我们刻画了满足C∪D=[0, m]{r₁}，C∩D={r₂}，且C与{0, m}交集非空时，R_C(n)=R_D(n)恒成立的充要条件。
• •
  定理1.1给出了上述结构完全由Thue-Morse序列及其平移决定的完整分类。

1. 引言

令N表示所有非负整数的集合。对于S?N和n∈N，用R_S(n)表示方程n = s₁+ s₂（其中s₁, s₂∈S且s₁< s₂）的解的个数。令A为在二进制表示中包含偶数个1的非负整数集合，B = N\A。集合A称为Thue-Morse序列。对于任意正整数l，令A_l= A ∩ [0, 2^l- 1]，B_l= B ∩ [0, 2^l- 1]。Sárk?zy提出问题：是否存在两个子集C, D?N，其对称差无限，且对所有足够大的整数n，都有R_C(n) = R_D(n)？Dombi利用Thue-Morse序列肯定地回答了该问题。随后，Lev、Sándor和Tang用不同方法证明了该结果。其他相关结果可参考文献。

设[a, b]表示所有满足a ≤ n ≤ b的整数n的集合。对于a∈N和S?N，a+S表示所有形如a+s（s∈S）的整数集合。对于任意整数r和m，定义r + mN = {r + mk: k∈N}。Chen和Lev证明了，对于任意给定的正整数l，存在子集C, D?N，满足C∪D=N，C∩D=2^2l-1 + (2^2l+1- 1)N，且对所有正整数n，R_C(n) = R_D(n)。他们提出了问题1。

问题1

已知R_C(n) = R_D(n) 对所有正整数n成立，C∪D=[0, m]，C∩D={r}，其中整数r≥0，m≥2。那么，是否必然存在一个正整数l，使得r = 2^2l- 1，m = 2^2l+1- 2，C = A_2l∪ (2^2l- 1 + B_2l) 且 D = B_2l∪ (2^2l- 1 + A_2l)？

2017年，Kiss和Sándor肯定地解决了问题1，得到了定理A。Kiss和Sándor也考虑了满足C∪D=[0, m]，C∩D=?，且R_C(n) = R_D(n)对所有非负整数n成立的集合C和D，得到了定理B。

2022年，Jiao, Sándor, Yang和Zhou考虑了满足C∪D=[0, m]{r}，C∩D=?，且R_C(n) = R_D(n)对所有非负整数n成立的集合C和D，得到了定理C。

近期，Sun和Pan以及Sun考虑了满足C∪D=[0, m]，C∩D={r₁, r₂}，且R_C(n) = R_D(n)对所有非负整数n成立的集合C和D，分别得到了定理D和定理E。

在本文中，我们考虑满足C∪D=[0, m]{r₁}，C∩D={r₂}，且R_C(n) = R_D(n)对所有非负整数n成立的集合C和D，得到了以下结果。

定理1.1

设m, r₁, r₂为整数，满足m ≥ 3 且 0 ≤ r₁, r₂≤ m。设C和D为两个非负整数集，满足C∪D=[0, m]{r₁}，C∩D={r₂}，且C ∩ {0, m} ≠ ?。那么，R_C(n) = R_D(n) 对所有非负整数n成立，当且仅当下列条件之一成立：

(1) 存在正整数l，使得r₁= 0，r₂= 2^2l，m = 2^2l+1- 1，且 C = (1 + B_2l) ∪ (2^2l+ A_2l), D = (1 + A_2l) ∪ (2^2l+ B_2l);

(2) 存在正整数l，使得r₁= 2^2l+1- 1，r₂= 2^2l- 1，m = 2^2l+1- 1，且 C = A_2l∪ (2^2l- 1 + B_2l), D = B_2l∪ (2^2l- 1 + A_2l).

在本文中，对于C, D?N，设C△D = (C\D) ∪ (D\C) 表示C和D的对称差。