主題
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)

另請參閱

完美差集, 完美尺規, 尺規, 稀疏尺規, 泰勒條件, 稱重

使用 探索

參考文獻

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/.

在 上被引用

Golomb 尺規

請引用為

Weisstein, Eric W. "Golomb 尺規。" 來自 Web 資源。 https://mathworld.tw/GolombRuler.html

主題分類