主题
Search

Golomb 尺规

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
GolombRulers

一个 n 刻度的 Golomb 尺规是一组 n 个不同的非负整数 (a_1,a_2,...,a_n)，称为“刻度”，使得所有可能的不同整数对 i,j=1, ..., n 且 i!=j 的正差值 |a_i-a_j| 都是不同的。

对于五个或更多刻度的 Golomb 尺规，不存在 完美 Golomb 尺规，即能够唯一测量直至其长度的所有距离的 Golomb 尺规（Golomb 1972；Gardner 1983, p. 154）。

设 a_n 为 n 刻度的 Golomb 尺规中的最大整数。那么一个 n 刻度的 Golomb 尺规 (0,...,a_n) 是最优的，如果

1. 不存在其他 n 刻度的 Golomb 尺规具有更小的最大刻度 a_n，并且

2. 该尺规以规范形式书写，作为等价尺规 (0,a_2,...,a_n) 和 (0,...,a_n-a_2,a_n) 中的“较小”者，其中“较小”意味着第一个不同的条目小于另一个尺规中的相应条目。

在这种情况下，a_n 被称为最优 n 刻度尺规的“长度”。

因此，(0, 1, 3) 是唯一的模反转最优 3 刻度 Golomb 尺规（即，(0, 2, 3) 被认为是相同的尺规）。

例如，集合 (0, 1, 3, 7) 是 4 刻度 Golomb 尺规，因为它的差值是 (1=1-0, 2=3-1, 3=3-0, 4=7-3, 6=7-1, 7=7-0)，所有这些都是不同的。然而，唯一的最优 Golomb 4 刻度尺规是 (0, 1, 4, 6)，它可以测量距离 (1, 2, 3, 4, 5, 6)。再举一个例子，事实证明最优 6 刻度 Golomb 尺规的长度是 17。实际上，总共有四个不同的长度为 17 的 6 刻度 Golomb 尺规，其中一个由 (0, 1, 4, 10, 12, 17) 给出。

尺规可以通过给出刻度出现的位置（例如，上面示例中的 (0, 1, 3, 7)）或连续刻度之间的差异来表示，在本例中，差异将是 [1,2,4]。

对于 n 刻度的 Golomb 尺规，当 n=2, 3, 4, ... 时，最优长度分别为 1, 3, 6, 11, 17, 25, 34, ... (OEIS A003022, Vanderschel 和 Garry)。虽然对于 n 刻度的 Golomb 尺规，当 n>28 时，最优长度尚不清楚，但在 1998 年至 2023 年间，Golomb 尺规搜索项目证明了已知的 21 至 28 刻度尺规是最优的。

证明 Golomb 尺规的最优性是出了名的困难。例如，在 1967 年，J. P. Robinson 和 A. J. Bernstein 发现了 24 刻度尺规 (0, 9, 33, 37, 38, 97, 122, 129, 140, 142, 152, 191, 205, 208, 252, 278, 286, 326, 332, 353, 368, 384, 403, 425)，该尺规在 2004 年 11 月 1 日通过在distributed.net上进行为期 4 年的计算而被验证为最优，该计算对 555529785505835800 个尺规进行了穷举搜索 (distributed.net 2004)。1984 年，M. D. Atkinson 和 A. Hassenklover 发现了 25 刻度尺规 (0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207, 214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480)。随后的八年distributed.net针对 25 刻度尺规的项目，在 124387 人的协助下，于 2008 年 10 月 25 日宣布 25 刻度尺规是最优的。

Dimitromanolakis (2002)、Drakakis (2009) 以及 Rokicki 和 Dogon 对 Golomb 尺规的构造方法进行了综述。正如 Rokicki 和 Dogon 所指出的，Singer (1938) 开发的技术，以及 Bose (1942) 和 Bose 和 Chowla (1962-63) 的一些后续研究，产生的尺规保证接近最优，看起来是最优的，并且除了六个小尺寸外，已经产生了所有已知的最优尺规（参见 Pegg 2016）。

对于 n 刻度的 Golomb 尺规，不等价最优尺规的数量 N(n)，当 n=2, 3, ... 时，分别为 1, 1, 1, 2, 4, 5, 1, 1, 1, ... (OEIS A036501)，最优 n 刻度尺规中的距离数量由三角形数 T_n=n(n-1)/2 给出，因此对于 n=1, 2, ..., 前几个是 0, 1, 3, 6, 10, 15, ... (OEIS A000217)。

下表给出了小 n 的最优 Golomb 尺规的完整列表。J. B. Shearer 维护着一个更完整的表格。

nN(n)最优尺规
21(0, 1)
31(0, 1, 3)
41(0, 1, 4, 6)
52(0, 1, 4, 9, 11), (0, 2, 7, 8, 11)
64(0, 1, 4, 10, 12, 17), (0, 1, 4, 10, 15, 17), (0, 1, 8, 12, 14, 17),
(0, 1, 8, 11, 13, 17)
75(0, 1, 4, 10, 18, 23, 25), (0, 2, 3, 10, 16, 21, 25), (0, 1, 11, 16, 19, 23, 25),
(0, 1, 7, 11, 20, 23, 25), (0, 2, 7, 13, 21, 22, 25)
81(0, 1, 4, 9, 15, 22, 32, 34)

另请参阅

完美差集, 完美尺规, 尺规, 稀疏尺规, 泰勒条件, 称重

使用 Wolfram|Alpha 探索

参考文献

Atkinson, M. D.; Santoro, N.; and Urrutia, J. "Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for Nonlinear Repeaters." IEEE Trans. Comm. 34, 614-617, 1986.Bose, R. C. "An affine analogue of Singerâ-™s theorem. J. Indian Math. Soc. 6, 1-15, 1942.Bose, R. C. and Chowla, S. "Theorems in the Additive Theory of Numbers." Comment. Math. Helvet. 37, 141-147, 1962-63.Colbourn, C. J. and Dinitz, J. H. (编). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 315, 1996.Dewdney, A. K. "Computer Recreations." Sci. Amer. 253, 16, June 1985.Dewdney, A. K. "Computer Recreations." Sci. Amer. 254, 20, Mar. 1986.Dimitromanolakis, A. "Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers." 克里特技术大学。电子与计算机工程系。2002 年 6 月。distributed.net. "Project OGR." http://www.distributed.net/ogr/.distributed.net. "distributed.net Is Proud to Announce the Completion of OGR-24." 2004 年 11 月 1 日。 http://n0cgi.distributed.net/cgi/planarc.cgi?user=nugget&plan=2004-11-01.10:24.Drakakis, K. "A Review of the Available Construction Methods for Golomb Rulers." Adv. Math. Commun. 3, 235-250, 2009.Gardner, M. Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 153-155, 1983., M. The Magic Numbers of Dr Matrix. Buffalo, NY: Prometheus, p. 230, 1985.Golomb, S. W. "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.Guy, R. K. "Modular Difference Sets and Error Correcting Codes." §C10 in Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 181-183, 2004.Hewgill, G. "distributed.net OGR Project." http://www.hewgill.com/ogr/.Kotzig, A. and Laufer, P. J. "Sum Triangles of Natural Numbers Having Minimum Top." Ars. Combin. 21, 5-13, 1986.Lam, A. W. and Sarwate, D. V. "On Optimum Time Hopping Patterns." IEEE Trans. Comm. 36, 380-382, 1988.Miller, L. "Golomb Rulers." http://www.cuug.ab.ca/~millerl/g3-records.html.Pegg, E. Jr. "Math Games: Rulers, Arrays, and Gracefulness." 2004 年 11 月 15 日。 http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html.Pegg, E. Jr. "Golomb Rulers and Fibonacci Sequences." Wolfram Demonstrations Project. 2016. https://demonstrations.wolfram.com/GolombRulersAndFibonacciSequences/.Pegg, E. Jr. "Golomb Rulers." Wolfram Demonstrations Project. 2023. https://demonstrations.wolfram.com/GolombRulers/.Robinson, J. P. and Bernstein, A. J. "A Class of Binary Recurrent Codes with Limited Error Propagation." IEEE Trans. Inform. Th. 13, 106-113, 1967.Rokicki, T. and Dogon, G. "Possibly Optimal Golomb Rulers Calculated for 160 to 40,000 Marks." https://cube20.org/golomb/.Shearer, J. B. "Golomb Rulers." http://www.research.ibm.com/people/s/shearer/grule.html.Singer, J. "A Theorem in Finite Projective Geometry and Some Applications to Number Theory." Trans. Amer. Math. Soc. 43, 377-385, 1938.Sloane, N. J. A. Sequences A000217/M2535, A003022/M2540, A036501, and A039953 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M2540 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Vanderschel, D. and Garry, M. "In Search of the Optimal 20, 21, & 22 Mark Golomb Rulers." http://members.aol.com/golomb20/.

在 Wolfram|Alpha 上被引用

Golomb 尺规

请引用为

Weisstein, Eric W. "Golomb 尺规。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GolombRuler.html

主题分类