🔢 mathematics

New lower bounds for constant-weight codes via seeded bit-swap tabu search

이 논문은 시드 비트 스왑 타부 서치(seeded bit-swap tabu search)를 사용하여 이진 상수 가중 코드(binary constant-weight codes)에 대한 124개의 새로운 구성을 제시하며, 이는 $A(n,d,w)$ 에 대한 기존 하한을 개선하고 결과적으로 32, 33, 34, 37 차원에 대한 키싱 수(kissing numbers)의 하한을 향상시킨다.

원저자: William Echols

게시일 2026-08-17

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: William Echols

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 여행을 위해 여행 가방을 싸려고 한다고 상상해 보십시오. 하지만 아주 이상한 규칙이 하나 있습니다. 모든 물건은 반드시 크기가 정확히 같아야 하며, 어떤 두 물건도 서로 너무 비슷해서는 안 된다는 것입니다. 만약 물건들이 너무 비슷하면 어두운 곳에서 뒤섞여 혼란을 초래할 수 있기 때문입니다. 디지털 통신의 세계에서 이 '여행 가방'은 메시지이고, '물건'은 0과 1의 패턴(비트)이며, '크기'는 패턴에 들어있는 1의 개수입니다. 이것이 바로 **정해진 무게 부호(constant-weight codes)**라는 퍼즐입니다. 과학자들은 와이파이나 심우주 무선 통신처럼 노이즈가 많은 채널을 통해 데이터를 안정적으로 전송하기 위해 이 부호들을 사용하며, 이를 통해 몇 개의 비트가 뒤섞이더라도 수신자가 무엇이 전송되었는지 파악할 수 있도록 합니다. 목표는 단순하지만 매우 어렵습니다. 즉, 최대한 많은 고유하고 구별되는 아이템을, 서로 부딪히지 않게 하면서도 여행 가방 안에 담아내는 것입니다. 가방이 커질수록(더 많은 코드를 넣을 수 있을수록), 한 번에 더 많은 정보를 보낼 수 있습니다.

윌리엄 에클스(William Echols)는 이 패킹 문제를 영리한 방식으로 해결하기로 했습니다. 빈 가방에서 시작해 아이템을 무작위로 던져 넣으며 맞기를 바라는 대신, 그는 "시드(seeded)" 방식을 사용했습니다. 이것을 이렇게 생각해 보십시오. 만약 당신이 더 나은 레고 성을 만들고 싶다면, 처음부터 다시 시작하는 것이 아니라 이미 훌륭한 기존의 성을 가져와서, 브릭 몇 개를 빼내고 교체해 보며 더 크거나 더 튼튼하게 만들 수 있는지 확인하는 것과 같습니다. 에클스는 **타부 탐색(tabu search)**이라는 컴퓨터 기법을 사용했는데, 이는 마치 자신이 지나온 길을 되돌아가지 않기로 결심한(루프에 빠지는 것을 피하기 위해) 아주 고집 센 탐험가와 같습니다. 그는 기존의 고품질 코드 설계를 탐험가에게 "시드"로 제공하여, 그가 새로운 경로를 찾도록 유도했습니다. 그는 이 방식을 통해 이전에 발견된 적 없는 124개의 새로운, 더 큰 패킹 배열을 찾아냈습니다. 이 새로운 배열들은 우리가 한 번에 보낼 수 있는 메시지의 하한선(lower limits)을 개선하며, 심지어 고차원 공간에서 얼마나 많은 구체가 중심 구체를 둘러쌀 수 있는지에 대한 개념인 "키싱 넘버(kissing numbers)"를 이해하는 데에도 도움을 줍니다.

패킹 퍼즐과 마법의 씨앗

디지털 세계에서 데이터는 그저 0과 1로 이루어진 긴 문자열일 뿐입니다. 때때로 데이터를 견고하게 만들기 위해, 우리는 특정 개수의 1만을 가진 문자열만을 허용합니다. 예를 들어, "무게"가 5라고 한다면, 모든 문자열은 반드시 정확히 5개의 1을 가져야 하며 나머지는 0이어야 합니다. 이제 당신에게 이러한 문자열들의 모음이 있다고 상상해 보십시오. 오류를 방지하기 위해, 당신의 모음에 있는 모든 문자열은 다른 모든 문자열과 충분히 달라야 합니다. 만약 두 문자열이 너무 비슷하면, 약간의 노이즈가 발생했을 때 하나의 문자열이 다른 하나로 변할 수 있어 수신자가 혼동을 일으킬 수 있습니다. 이들 사이의 "거리"는 얼마나 많은 위치가 다른지로 측정됩니다.

이 분야의 핵심 질문은 다음과 같습니다: 당신의 모음에 담을 수 있는 문자열의 최대 개수는 얼마인가? 이 최대 숫자를 $A(n, d, w)$ 라고 부르며, 여기서 $n$ 은 문자열의 길이, $d$ 는 필요한 최소 거리, $w$ 는 1의 개수입니다. 수십 년 동안 수학자와 컴퓨터 과학자들은 다양한 설정에 대해 가장 큰 규모의 모음을 찾기 위해 노력해 왔습니다. 그들은 훌륭한 모음들을 찾아냈지만, 그것이 절대적인 최대치인지 여부는 종종 알지 못했습니다. 그들은 단지 자신들이 할 수 있는 최선의 결과가 이 정도라는 것만 알 뿐이었습니다.

"시딩(Seeding)" 전략

이러한 최대 숫자를 찾기 위한 이전의 시도들은 컴퓨터 검색을 이용했을 때 마치 어두운 숲속을 헤매는 것처럼 느껴지곤 했습니다. 컴퓨터는 무작위 추측으로 시작하며, 때로는 좋은 경로를 찾기도 하지만, 종종 산 정상처럼 보이지만 실제로는 정상이 아닌 국소적 지점(local clearings)에 갇히곤 했습니다. 그들은 그곳에서 멈춰 서서 최고의 코드를 찾았다고 생각했지만, 사실 훨씬 더 큰 코드가 바로 다음 언덕 너머에 있었습니다.

에클스는 처음부터 다시 시작하는 것이 문제의 핵심임을 깨달았습니다. 그는 시드 초기화(seeded initialization) 기술을 사용했습니다. 무작위 시작점을 생성하는 대신, 그는 기존의 고품질 코드(하나의 "시드")를 가져와 이를 바탕으로 탐색을 시작했습니다.

그는 두 가지 재미있는 방식으로 이를 수행했습니다:

직접 시딩(Direct Seeding): 그는 기존의 코드를 가져와서, "문제(distance deficits)"를 가장 적게 일으키도록 신중하게 선택된 하나의 단어를 추가했습니다. 이는 약간 더 크고, 약간은 지저도 있는 시작점을 만들어냈습니다.
이웃 시딩(Neighbor Seeding): 그는 약간 다른 문제에 대한 코드들을 살펴보았습니다. 예를 들어, 길이가 30인 코드를 원한다면, 길이가 29인 훌륭한 코드를 가져와 모든 단어에 0을 하나씩 추가하여 길이를 30으로 만든 뒤 이를 시작점으로 사용했습니다. 또는 길이가 31인 코드를 가져와 0 하나를 잘라내어 사용할 수도 있었습니다.

이러한 "시딩된" 시작점을 확보한 후, 그는 **비트 스왑 타부 탐색(bit-swap tabu search)**을 실행했습니다. 이 탐색을 문자열 내의 1의 위치를 의자라고 생각하는 '의자 뺏기 게임'이라고 상상해 보십시오. 알고리즘은 비트를 교체하며 문자열들을 더 뚜렷하게 만들려고 시도합니다. "타부(tabu)" 부분은 알고리즘이 방금 수행한 움직임을 기억하고 이를 즉시 되돌리는 것을 거부함으로써, 제자리를 맴도는 대신 새로운 영역을 탐색하도록 강제한다는 것을 의미합니다.

결과: 124개의 새로운 발견

이 스마트한 시딩 전략을 통해, 에클스는 이전의 최고 기록을 경신한 124개의 새로운 구조를 찾아냈습니다. 이것들은 단순히 작은 개선이 아닙니다. 어떤 것들은 엄청난 도약입니다.

예를 들어:

특정 제약 조건이 있는 길이 39의 코드의 경우, 이전의 최고 기록은 1,014개였습니다. 새로운 방법은 1,118개의 단어를 찾아냈습니다. 무려 104개의 이득입니다!
길이 40의 경우, 기록이 1,170에서 1,230으로 뛰었습니다.
길이 56의 경우, 숫자가 2,414에서 2,477로 증가했습니다.

이 숫자들은 해당 설정에 대해 우리가 혼동 없이 보낼 수 있다고 확실히 보장할 수 있는 고유한 메시지의 최대 개수를 나타냅니다. 이 논문은 이것들이 반드시 가능한 절대적인 최대치(진정한 수학적 한계)라고 주장하는 것은 아니지만, 우리가 생각했던 것보다 분명히 더 잘할 수 있다는 것을 증명합니다. 이는 "하한선(lower bound)"을 높여주며, 즉 우리는 이만큼의 아이템을 가방에 담을 수 있다는 것을 확실히 알게 해줍니다.

키싱 넘버: 놀라운 부수 효과

이야기는 여기서 더욱 흥도있게 진행됩니다. 이 논문은 **키싱 넘버(kissing numbers)**라는 개념도 다룹니다. 방 한가운데에 거대한 공 하나가 있다고 상상해 보십시오. 서로 겹치지 않으면서 중심 공에 닿을 수 있도록 같은 크기의 다른 공들을 중심 공 주변에 얼마나 많이 배치할 수 있을까요? 3차원 공간에서 답은 12입니다. 하지만 고차원(예: 32차원 또는 33차원)에서는 답을 찾기가 훨씬 더 어렵습니다.

이러한 키싱 넘버에 대한 수학은 에클스가 찾은 정해진 무게 부호와 깊게 연결되어 있습니다. 그가 특정 매개변수(특히 $A(n, 8, 8)$ )에 대한 코드를 개선했기 때문에, 그는 32, 33, 34, 37차원의 키싱 넘버에 대한 하한선을 자동으로 개선했습니다.

예를 들어, 32차원( $\tau_{32}$ )의 경우, 이전의 추정치는 적어도 345,408개의 공이 중심 공에 닿을 수 있다는 것이었습니다. 새로운 코드를 통해 이 숫자는 346,432로 증가했습니다. 이는 작은 비율의 증가이지만, 고차원 기하학의 세계에서 더 많은 공을 끼워 넣을 수 있다는 것을 찾아내는 것은 중대한 승리입니다.

요점

윌리엄 에클스는 단순히 몇 개의 더 나은 코드를 찾은 것이 아닙니다. 그는 눈을 가린 채 처음부터 시작하는 대신, 기존의 지식으로부터 "시드"를 사용하는 방식으로 검색을 시작하는 것이 얼마나 영리한 방법인지를 보여주었습니다. 이 논문은 124개의 구체적인 개선이 가능하다는 것을 입증하며, 우리가 이러한 디지털 문자열 안에 얼마나 많은 데이터를 안정적으로 채울 수 있는지에 대한 새로운, 더 높은 바닥(floor)을 제시합니다. 이는 때때로 모든 것을 밑바닥부터 쌓아 올리려 하기보다, 이미 우리가 알고 있는 것들의 어깨 위에 올라서는 것이 더 나은 전진 방법임을 상기시켜 줍니다.

기술 요약: 시드 기반 비트 스왑 타부 서치(Seeded Bit-Swap Tabu Search)를 통한 새로운 상수 가중치 코드 하한값

문제 정의
본 논문은 이진 상수 가중치 코드(binary constant-weight codes)의 구축 문제를 다룬다. 이 코드는 길이가 $n$ 이고 각 단어의 해밍 가중치(Hamming weight)가 고정된 $w$ 이며, 최소 쌍 해밍 거리(minimum pairwise Hamming distance)가 $d$ 인 이진 단어들의 집합으로 정의된다. 핵심 목표는 $A(n, d, w)$ , 즉 이러한 코드의 최대 크기를 결정하는 것이다. 기존에도 다양한 파라미터 세트에 대해 상당한 계산적 노력이 투입되어 하한값을 확립해 왔으나, 더 강력한 하한값을 찾는 것은 여전히 어려운 조합 최적화 문제로 남아 있다. 표준 타부 서치를 포함한 기존의 메타휴리스틱 접근 방식들은 역사적으로 알려진 값보다 약한 결과를 냈던 한계가 있었다.

방법론
저자는 로진(Rosin)의 비트 스왑 타부 서치 알고리즘[8]에 시드 초기화(seeded initialization) 전략을 도입하여 이를 수정할 것을 제안한다. 무작위로 생성된 단어들로 탐색을 초기화하는 대신, 이 방법은 동일하거나 인접한 파라미터를 가진 기존 코드로부터 단어를 가져와 탐색을 "웜 스타트(warm-start)"한다.

이 방법론은 두 가지 주요 시딩(seeding) 기법을 포함한다:

직접 시딩(Direct Seeding): 대상 $(n, d, w)$ 에 대해, 알고리즘은 동일한 파라미터를 가진 기존 코드 $S$ 를 활용한다. 알고리즘은 누적 "거리 결핍 페널티"(최소 거리 제약 조건의 위반 합계)를 최소화하는 단어 $v$ 를 $S$ 에 추가함으로써 초기화 세트의 라이브러리를 구성한다. 그 후, 이 라이브러리에서 무작위 샘플링을 사용하여 비트 스왑 타부 서치를 최대 $4|E|$ 회(여기서 $E$ 는 최소 결핍 단어의 집합) 실행한다. 결정적인 점은, 제공된 시드를 보존하기 위해 재시작(restart) 메커니즘을 생략한다는 것이다.
이웃 시딩(Neighbor Seeding): 이 기법은 인접한 파라미터 세트의 코드를 활용하여 인증(certificate)을 강화한다.
- 연장(Lengthening): $A(n-1, d, w)$ 에 대한 기존 인증을 길이 $n$ 으로 확장한다.
- 단축(Shortening): $A(n+1, d, w)$ 의 인증에서 하나의 좌표(zero-slice)를 제거하여 길이 $n$ 의 단어들을 형성한다.
  이러한 중간 단계의 코드들은 종종 목표 크기 $s$ 보다 작으므로, 알고리즘은 최소 페널티를 가진 무작위 단어들로 이를 패딩(padding)한다. 이는 일시적으로 최소 거리 속성을 위반하지만, 이후의 비트 스왑 타부 서치가 해당 집합을 유효한 코드로 복구한다.

구현 과정에서는 매 삽입 시마다 최소 결핍 집합 $E$ 를 다시 계산하는 계산적 부하를 피하기 위해, 처음에 $E$ 를 계산하고 이를 복원 추출(sampling with replacement) 방식으로 균등하게 샘플링한다. 이 알고리즘은 자신의 출력값에 연속적으로 적용되도록 설계되었으며, 반복 간에 서로 다른 시딩 방법을 사용하여 지역 최적점(local optima)을 탈출하도록 한다.

주요 기여 및 결과
본 연구의 주요 기여는 기존의 하한값을 개선하는 **124개의 새로운 구축(constructions)**을 발견한 것이다. 이 결과들은 브라우어(Brouwer)의 온라인 테이블[2]을 통해 검증되었다.

상수 가중치 코드: 논문의 표 1은 광범위한 파라미터에 걸친 개선 사항을 상세히 기술한다. 주목할 만한 이득은 다음과 같다:
- $A(39, 8, 7)$ 이 1014에서 1118로 개선 (+104).
- $A(40, 8, 7)$ 이 1170에서 1230으로 개선 (+60).
- $A(56, 6, 5)$ 가 2414에서 2477로 개선 (+63).
- $d=10$ 및 다양한 가중치를 포함하는 파라미터에서도 유의미한 개선이 관찰되었다.
키싱 넘버(Kissing Numbers): $n \in \{32, 33, 34, 37\}$ $n \in {32, 33, 34, 37}$ 에 대한 $A(n, 8, 8)$ $A (n, 8, 8)$ 의 개선된 하한값으로부터 직접적인 결과로서, 본 논문은 개선된 키싱 넘버 $\tau_n$ $τ_{n}$ 의 하한값을 도출한다. 구체적으로:
- $\tau_{32}$ 가 345,408에서 346,432로 개선 (+1,024).
- $\tau_{33}$ 이 360,640에서 362,048로 개선 (+1,408).
- $\tau_{34}$ 가 380,868에서 381,124로 개선 (+256).
- $\tau_{37}$ 이 494,312에서 496,232로 개선 (+1,920).

의의 및 주장
본 논문은 제안된 시드 기반 초기화 접근 방식이 이전에 더 약한 하한값을 냈던 기존 타부 서치 구현의 한계를 효과적으로 극복함을 주장한다. 관련 코딩 문제에서 유도된 고품질의 시드로 메타휴리스틱을 "웜 스타트"함으로써, 무작위 초기화가 실패했던 지점에서 더 강력한 하한값을 찾아내는 데 성공했다. 본 연구는 관련 조합 코딩 이론의 고품질 시드를 활용한 "웜 스타트"가 즉각적이고 검증 가능한 개선을 가져올 수 있음을 보여주는 실질적인 사례이다. 저자는 추가적인 검증과 연구를 용이하게 하기 위해 생성된 코드들을 공개적으로 제공한다.

패킹 퍼즐과 마법의 씨앗

"시딩(Seeding)" 전략

결과: 124개의 새로운 발견

키싱 넘버: 놀라운 부수 효과

요점

유사한 논문