골롬 자

수학에서 골롬 자(Golomb leader)는 두 쌍의 표식이 같은 거리를 가지지 않도록 자를 따라 정수 위치에 있는 표식을 말한다.자에 있는 표시의 수는 순서가 되고, 두 자 사이의 가장 큰 거리는 길이가 된다.골롬 통치자의 번역과 반사는 사소한 것으로 여겨지기 때문에, 가장 작은 마크는 관례적으로 0으로, 다음 마크는 가능한 두 값 중 작은 값으로 넣는다.골롬 지배자는 코스타스 배열의 1차원 특수 사례로 볼 수 있다.

골롬의 지배자는 솔로몬 W. 골롬의 이름을 따서 지었고, 시돈(1932년)^[1]과 밥콕(1953년)에 의해 독자적으로 발견되었다.^[2]소피 피카르도 1939년 이 세트들에 대한 초기 연구를 발표하면서, 같은 거리 세트를 가진 두 골롬 지배자가 일치해야 한다는 주장을 정리했다.이것은 6개항의 통치자들에게는 거짓으로 밝혀졌지만, 그렇지 않은 경우에는 사실이다.^[3]

골롬 통치자가 길이까지 모든 거리를 측정할 수 있다는 요건은 없지만, 그렇게 되면 완벽한 골롬 통치자라고 불린다.5점 이상의 완벽한 골롬 지배자는 존재하지 않는다는 것이 증명되었다.^[4]같은 질서의 더 짧은 골롬 지배자가 존재하지 않는다면 골롬 지배자가 최적이다.골롬 지배자를 만드는 것은 쉽지만, 특정 질서에 대한 최적의 골롬 지배자(또는 지배자)를 증명하는 것은 계산적으로 매우 어려운 일이다.

분산되다.net은 최적의 순서-24에 대한 분산 병렬 검색을 완료했으며, 매번 후보자로 의심되는 자를 확인하는 순서-27 Golomb 통치자를 통해 최적의 순서-24를 검색했다.^[5][6][7][8]2014년 2월 아마존닷컴은 order-28의 최적 골롬 지배자(OGR)를 찾기 위한 수색을 시작했다.완성은 2021년 11월 현재 발표되지 않았다.^[9]

현재 임의 순서 n(n이 단수로 주어지는 곳)의 OGR을 찾는 복잡성은 알려져 있지 않다.과거에는 그것이 NP-hard 문제라는 약간의 추측이 있었다.^[4]골롬 지배자의 건설과 관련된 문제들은 NP-hard로 분명히 나타나는데, 여기서 알려진 NP-완전한 문제는 골롬 지배자를 찾는 것과 비슷한 풍미를 가지고 있지 않다는 것도 주목되고 있다.^[10]

정의들

골롬 지배자 세트

$A{\displaystyle }$=${\displaystyle }${ ${\displaystyle {a\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{2\mathrm{}}_{}}$, .. , ${\displaystyle m_{}}$ ${\displaystyle {}_{}}$ ${\$$displaystyle$ $A=\{a_{1},$$a_{$$2},$ $여기$서 < . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .$<a_{m}}>$는 만약의 경우에 한해서만 골롬 자다.

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ and }}j=l.}$^[11]

그러한 골롬 자자의 순서는 $m{\displaystyle }$ ${\displaystyle m}$이고 길이는 ${\displaystyle m_{}}$- ${\displaystyle {1\mathrm{}}_{}}$ ${\$}이다$.$정식 형식은 ${\displaystyle 1{}_{}}$= 0 ${\displaystyle a_{1}=0}$이고 > ${\displaystyle m>$${\$ - ${\displaystyle a_{2}-a_{m}-a_{m-1$ 형식은 번역과 반사를 통해 얻을 수 있다.

함수로서의 골롬 지배자

An injective function ${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$ with ${\displaystyle f(1)=0}$ and ${\displaystyle f(m)=n}$ is a Golomb ruler if and only if

${\displaystyle{\displaystyle{\i,j,k,l\in \{1,2,...,m\right\}{\text{}}{}}}}{}\i\neq l,f(i)-f(k)-f(l)\f ik{{}j=l}.}$^{[12]: 236}

그러한 골롬 자자의 $순서$는 m ${\displaystyle m}$이고 길이는 $n{\displaystyle }$ ${\displaystyle n}$이다$.$표준 형식은 다음과 같다.

( ) $m$>2${\displaystyle$ m$>2 {\displaystyle m$>$2$ .

최적성

골롬의 질서의 지배자m길이로n다음 두 가지 측면에서 최적일 수 있다.^{[12]: 237}

• 최적으로 밀도가 높아 최대치를 나타낼 수 있다.m의 특별한 가치를 위하여n,
• 최적으로 짧을 수도 있고, 최소로 보일 수도 있다.n의 특별한 가치를 위하여m.

일반 용어 최적 골롬 눈금자는 두 번째 유형의 최적성을 가리킬 때 사용된다.

실용적 응용

정보이론 및 오류수정

골롬 지배자는 오류 수정 코드와 관련된 정보 이론 내에서 사용된다.^[14]

무선 주파수 선택

골롬 지배자는 지상^[15] 및 외계^[16] 애플리케이션과의 상호변조 간섭의 영향을 줄이기 위해 무선 주파수 선택에 사용된다.

무선 안테나 배치

골롬 눈금자는 단계별 무선 안테나 배열 설계에 사용된다.[0,1,4,6] 골롬 눈금자 구성의 안테나는 AM 타워나 셀 현장에서 흔히 볼 수 있다.무선 천문학에서 1차원 합성 배열은 푸리에 성분 샘플링의 최소 중복성을 얻기 위해 골롬 눈금자 구성으로 안테나를 가질 수 있다.^[17][18]

전류 변압기

다중 비율의 전류 변압기는 골롬 눈금자를 사용하여 변압기 탭 포인트를 배치한다.

시공방법

많은 건설 방법들이 점증적으로 최적의 골롬 지배자를 만들어낸다.

에르데스-투란 건설

폴 에르디스와 팔 투란 때문에 다음 건축물은 홀수 p마다 골롬 지배자를 생산한다.^[13]

${\displaystyle 2pk+(k^{2}\,{\bmod {\,}p),k\in [0,p-1]}$

알려진 최적의 골롬 지배자

다음 표에는 역순으로 표시가 있는 자를 제외한, 알려진 모든 최적 골롬 통치자가 수록되어 있다.처음 네 개는 완벽해.

주문	길이	흔적들	증명된[*]	발견된 증거:
1	0	0	1952[19]	월리스 배콕
2	1	0 1	1952[19]	월리스 배콕
3	3	0 1 3	1952[19]	월리스 배콕
4	6	0 1 4 6	1952[19]	월리스 배콕
5	11	0 1 4 9 11 0 2 7 8 11	c. 1967년[20]	존 P. 로빈슨과 아서 J. 번스타인
6	17	0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17	c. 1967년[20]	존 P. 로빈슨과 아서 J. 번스타인
7	25	0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25	c. 1967년[20]	존 P. 로빈슨과 아서 J. 번스타인
8	34	0 1 4 9 15 22 32 34	1972[20]	윌리엄 믹슨
9	44	0 1 5 12 25 27 35 41 44	1972[20]	윌리엄 믹슨
10	55	0 1 6 10 23 26 34 41 53 55	1972[20]	윌리엄 믹슨
11	72	0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72	1972[20]	윌리엄 믹슨
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979[20]	존 P. 로빈슨
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981[20]	존 P. 로빈슨
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985[20]	제임스 B.시어러
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985[20]	제임스 B.시어러
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986[20]	제임스 B.시어러
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993[20]	W. 올린 시버트
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993[20]	W. 올린 시버트
19	246	0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246	1994[20]	아포톨로스 돌라스, 윌리엄 T랭킨과 데이비드 맥크라켄
20	283	0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283	1997?[20]	마크 개리, 데이비드 밴더스첼 외 연구진(웹 프로젝트)
21	333	0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333	1998년[21] 5월 8일	마크 개리, 데이비드 밴더스첼 외 연구진(웹 프로젝트)
22	356	0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356	1999[20]	마크 개리, 데이비드 밴더스첼 외 연구진(웹 프로젝트)
23	372	0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372	1999[20]	마크 개리, 데이비드 밴더스첼 외 연구진(웹 프로젝트)
24	425	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년[5] 10월 13일	분산된그물을 치다
25	480	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	2008년[6] 10월 25일	분산된그물을 치다
26	492	0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492	2009년[7] 2월 24일	분산된그물을 치다
27	553	0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553	2014년[8] 2월 19일	분산된그물을 치다

^{^ *} 최적의 통치자는 이 날짜 이전에 알려졌을 것이다; 이 날짜는 그것이 최적인 것으로 발견된 날짜를 나타낸다(다른 모든 통치자들은 더 작지 않은 것으로 증명되었기 때문이다).예를 들어, 순서 26에 최적으로 판명된 자를 2007년 10월 10일에 기록했지만, 2009년 2월 24일에 다른 모든 가능성이 소진되기 전까지는 최적이라고 알려져 있지 않았다.

참고 항목

• 코스타스 배열
• 분산 컴퓨팅
  • BOINC
  • 분산된그물을 치다
• 퍼펙트 자
• 시돈 수열
• 희소자

참조

• Gardner, Martin (March 1972). "Mathematical games". Scientific American. 226 (3): 108–112. doi:10.1038/scientificamerican0372-108.

외부 링크

• 제임스 B.시어러스의 골롬 통치자 페이지
• 분산된net: 프로젝트 OGR
• 최적의 20, 21, 22 마크 골롬 지배자를 찾아서
• 200개 이상의 길이에 이르는 골롬