On Base , Normal and Near-normal Sequences

조합 수학의 조용하고 추상적인 세계에서, 연구자들은 종종 단순한 숫자 목록 속에 숨겨진 패턴을 찾아 헤맵니다. 스위치가 "켜짐" 또는 "꺼짐" 중 하나로 설정된 긴 스위치 행들을 상상해 보십시오. 만약 여러분이 두 개의 그러한 행을 가져와서, 하나를 다른 하나 위로 미끄러지듯 움직이며 비교한다면, 모든 단계에서 얼마나 일치하거나 어긋나는지를 측정할 수 있습니다. 이 측정값을 자기상관(autocorrelation)이라고 부릅니다. 수십 년 동안 수학자들은 특정한 퍼즐에 매료되어 왔습니다. 서로 다른 길이를 가진 두 쌍의 서로 다른 행 네 개를 찾아내어, 이들을 미끄러지듯 움직이며 일치와 어긋남을 모두 더했을 때, 맨 처음 시작 지점을 제외한 모든 곳에서 전체 소음이 완벽하게 0으로 상쇄될 수 있는가 하는 문제입니다. 이것이 바로 "기저 수열(base sequences)"에 대한 탐구입니다.

이 수열들은 단순히 숫자의 놀이가 아닙니다. 이들은 하다마드 행렬(Hadamard matrix)이라 불리는 특수한 형태의 정사각형 격자를 구축하기 위한 숨겨진 설계도입니다. 이러한 격자들은 공학 및 물리학에서 매우 중요한 도구로 사용되며, 소음이 많은 환경에서도 신호가 왜곡되지 않고 전달될 수 있도록 하는 신호를 만드는 데 쓰입니다. 마치 명확한 목소리가 붐비는 방을 뚫고 들려오는 것과 같습니다. 격자의 크기가 커질수록 신호는 더 강력해지지만, 이 격자를 만들기 위해 적절한 스위치 배열을 찾는 일은 크기가 증가함에 따라 기하급수적으로 어려워집니다. 오랫동안 수학자들은 이러한 완벽한 배열이 가능한 모든 크기에 대해 존재할 것이라는 강력한 직관, 즉 '추측'을 가지고 있었으나, 그들은 오직 특정 지점까지의 크기에 대해서만 이를 증명할 수 있었습니다.

난징 정보과학기술대학교의 한 연구팀은 이제 이 탐색의 경계를 전례 없는 수준으로 확장했습니다. 그들은 수십억 개의 가능한 스위치 행 조합을 걸러내기 위한 새롭고 매우 효율적인 방법을 개발했습니다. 이 알고리즘은 네 개의 행을 한꺼번에 추측하는 대신, 먼저 서로 잘 들어맞는 두 행의 쌍을 만든 다음, 세트를 완성하기 위한 나머지 두 행을 찾습니다. 이 접근 방식을 사용하여, 그들은 역사상 처음으로 크기 41, 42, 43에 대한 완벽한 수열을 성공적으로 구성해 냈습니다. 이 성과는 이러한 수열의 존재성에 대한 오랜 가설이 43까지의 모든 크기에 대해 참임을 확인시켜 주었으며, 이 수학적 구조의 알려진 영역을 확장했습니다.

그러나 연구진이 "근사 정규(near-normal)" 수열로 알려진 두 가지 더 엄격한 버전의 수열을 조사했을 때, 이야기는 놀라운 국면을 맞이합니다. 이 수열들의 경우, 모든 짝수에 대해 존재한다는 유사한 믿음이 있었습니다. 연구팀은 다음 몇 개의 짝수에 대해 이를 확인하기 위해 철저한 컴퓨터 탐색을 수행했습니다. 그 결과, 이 수열들이 많은 크기에서는 존재하지만, 42와 44에서는 단순히 존재하지 않는다는 것을 발견했습니다. 이 발견은 근사 정규 수열에 대한 믿음이 틀렸음을 구체적으로 보여준 첫 번째 실질적인 증거로서 매우 중요합니다. 이는 수학에서 오랫동안 유지되어 온 아이디어가 단지 증명되지 않은 것이 아니라, 실패하는 특정 사례를 찾아냄으로써 명시적으로 틀렸음이 밝혀진 드문 순간입니다.

연구진은 또한 "정규(normal)" 수열이라 불리는 또 다른 엄격한 버전을 조사했습니다. 그들은 이러한 수열이 특정 숫자 패턴, 즉 8의 배수보다 2 작은 숫자들에 대해서는 존재할 수 없음을 수학적으로 증명했습니다. 그들의 컴퓨터 탐색은 또한 41부터 46까지의 숫자들에 대해 이들이 존재하지 않음을 재확인했습니다. 그들이 일반적인 수열들은 성공적으로 구축해 냈지만, 더 엄격한 버전들의 존재 여부는 여전히 미스터리로 남아 있습니다. 이 연구는 단순히 목록에 새로운 예시를 추가하는 것이 아니라, 패턴이 어디에서 무너지고 어디에서 지속되는지를 보여줌으로써 가능한 것의 지형을 재편합니다.

이러한 발견의 영향은 서두에 언급한 하다마드 행렬의 구축으로 파급됩니다. 이 행렬들이 견고한 통신 시스템과 오류 정정 코드를 만드는 데 필수적이기 때문에, 어떤 크기를 만들 수 있고 어떤 크기를 만들 수 없는지 정확히 아는 것은 매우 중요합니다. 심오한 수학적 규칙과 강력한 컴퓨터 탐색을 결합한 연구진의 새로운 알고리즘은 앞으로 나아갈 명확한 경로를 제시합니다. 이를 통해 과학자들은 불가능한 조합을 빠르게 걸러낼 수 있다는 확신을 가지고 더 큰 크기를 테스트할 수 있습니다. 엄격한 유형에 대해서는 모든 크기에 대해 존재한다는 질문이 거짓으로 판명되었지만, 일반적인 탐구는 계속됩니다. 연구진은 이 복잡한 분야의 차세대 발견을 위한 길을 닦아 놓았습니다.