🔢 mathematics

A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

본 논문은 부분 합이 모두 서로 다른 $\mathbb{Z}/n\mathbb{Z}$ 의 순열의 개수를 세는 개선된 알고리즘을 제시하며, 특히 $n=20$ 과 $n=22$ 에 대한 결과를 계산하는 동시에 새로운 항의 도출을 가능하게 하는 알려진 수열과의 전단사 함수 관계를 확립한다.

원저자: Quinn Baker, Amy Feaver

게시일 2026-07-27

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Quinn Baker, Amy Feaver

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

당신이 거대한 파티에 있다고 상상해 보세요. 그곳의 모든 사람은 0부터 특정 한계치까지의 고유한 숫자가 적힌 티셔츠를 입고 있습니다. 주최자는 손님들을 사진을 찍기 위해 한 줄로 세우고 싶어 하지만, 까다로운 규칙이 하나 있습니다. 줄을 따라 걸어가면서 지금까지 본 숫자들의 누적 합계를 계속 기록해야 한다는 것입니다. 규칙은 새로운 사람을 합계에 추가할 때마다, 그 새로운 합계가 전체 줄에서 이전에 본 적 없는 숫자여야 한다는 것입니다. 만약 이미 계산했던 합계에 도달하게 되면, 줄은 깨지고 사진은 망가지게 됩니다. 이것은 단순한 파티 게임이 아니라, 수학의 세계에서 '군론(group theory)'이라고 불리는 깊은 퍼즐, 구체적으로는 숫자를 원형(시계의 시간처럼)으로 배열할 때 모든 숫자를 정확히 한 번씩 사용하면서도 누적 합계가 절대 중복되지 않도록 하는 방법과 관련이 있습니다. 수학자들은 이러한 특별한 줄을 찾는 것이 우주의 숨겨진 대칭성과 질서를 이해하는 데 도움이 된다는 점 때문에 이를 중요하게 여깁니다. 그리고 이러한 특별한 줄을 찾는 것은 모양이 계속 변하는 건초더미 속에서 특정한 바늘을 찾는 것만큼이나 놀라울 정도로 어렵습니다.

이 논문은 특정 유형의 숫자 원형에 대해 이 "누적 합계" 퍼즐을 해결하는 훨씬 더 똑똑한 방법을 찾아낸 수학자 팀에 관한 것입니다. 그들은 20시간이나 22시간이 있는 시계처럼 짝수 개의 칸이 있는 원형에 집중했습니다. 과거에는 이 원형들에 대해 유효한 줄이 얼마나 존재하는지 알아내기 위해 컴퓨터가 거의 모든 가능한 배치들을 하나하나 전부 확인해야 했습니다. 이는 좋은 사진을 얻기 위해 가능한 모든 사람의 조합을 일일이 불러 모으는 것과 같았으며, 이는 시간이 너무 오래 걸리고 규모가 커질수록 불가능해지는 일이었습니다. 베이커(Baker)와 피버(Feaver)는 마치 초능력을 가진 똑똑한 보안 요원처럼 작동하는 새로운 알고리즘을 도입했습니다. 이 보안 요원은 줄의 끝까지 기다렸다가 사진이 망가졌는지 확인하는 대신, 매 사람이 줄에 합류할 때마다 누적 합계를 즉시 확인합니다. 보안 요원이 이미 나타났던 합계를 발견하는 즉시, 해당 줄이 더 길어지는 것을 차단합니다. 그들은 만약 짧은 줄이 이미 깨졌다면, 그 깨진 시작 부분을 공유하는 모든 긴 줄 또한 결국 실패할 운명이라는 점을 깨달았습니다. 이러한 "나쁜" 가지들을 초기에 잘라냄으로써, 그들은 엄청난 시간을 절약했습니다.

이 효율적인 방법을 사용하여, 팀은 20개와 22개의 칸이 있는 원형에 대한 유효한 줄의 정확한 개수를 계산해 냈습니다. 그들은 20개 칸의 원형에 대해 정확히 5,074,931,072가지의 배열 방식이 있다는 것을 발견했습니다. 22개 칸의 경우, 그 숫자는 무려 298,557,044,000까지 치솟았습니다. 이 숫자들은 너무 컸기 때문에, 정확성을 보장하기 위해 다른 수학자인 버트 도벨레어(Bert Dobbelaere)에 의해 독립적으로 검증되어야 했습니다. 이 논문은 이러한 "누적 합계" 줄과 또 다른 개념인 "차집합(difference sets)" 사이의 매혹적인 연결 고리를 증명하며, 하나를 세는 것이 다른 하나를 세는 것과 정확히 같음을 보여줍니다. 이 증명은 그들이 한쪽의 성질을 이용해 다른 쪽을 해결할 수 있게 함으로써 효율성을 두 배로 높여주었습니다.

저자들은 자신들의 숫자가 엄격한 수학적 증명과 체계적으로 불가능한 옵션들을 제거하는 컴퓨터 탐색으로부터 도출되었기에 매우 확신하고 있습니다. 그러나 그들은 자신들의 방법이 가장 빠른 알려진 방식이긴 하지만, 이 문제는 여전히 믿기 힘들 정도로 어렵다는 점을 주의 깊게 언급합니다. 원형의 칸 수가 증가함에 따라 가능한 배열의 수는 너무 빠르게 늘어나서, 그들의 똑똑한 보안 요원조차 영원히 따라잡을 수 없습니다. 그들은 유효한 줄과 가능한 모든 줄의 비율이 점점 작아지며, 크기가 한 단계 올라갈 때마다 약 10배씩 감소한다고 제안합니다. 그들이 어떤 크기에 대해서도 즉각적으로 답을 예측할 수 있는 마법 같은 공식은 아직 찾지 못했지만, 그들의 연구는 우리가 멈추는 시점에 대해 더 영리하게 대처함으로써 우리가 알 수 있는 경계를 훨씬 더 멀리 밀어낼 수 있음을 증명합니다. 그들은 앞으로 나아가는 최선의 방법이 아마도 더 많은 "스마트한 지름길"을 찾아 몇몇 알려진 해답을 다른 모든 해답으로 연결하는 것이 될 것이라는 생각을 남기지만, 현재로서는 그들의 새로운 알고리즘이 이 수학적 걸작들을 세는 데 있어 가장 강력한 도구입니다.

기술 요약: $\mathbb{Z}/n\mathbb{Z}$ 의 부분 합이 모두 다른 순열의 개수를 찾는 더 효율적인 알고리즘

문제 정의
본 논문은 $n$ 이 짝수인 정수일 때, 정수 모듈로 $n$ 의 덧셈군( $\mathbb{Z}/n\mathbb{Z}$ ) 내에서 특정 순열의 개수를 열거하는 문제를 다룬다. 핵심 문제는 부분 합(또는 군의 맥락에서의 "계승(factorials)")이 모두 서로 다른 순열 $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ 의 개수를 세는 것이다. 구체적으로, 본 논문은 $\mathbb{Z}/2k\mathbb{Z}$ 의 순열에 대해 차집합(difference sets)의 개수를 세는 OEIS(온라인 정수 수열 사전)의 수열 A141599에 초점을 맞춘다.

차집합이 존재한다는 것은 $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ ( $1 \le i \le n-1$ )의 값들이 $\mathbb{Z}/n\mathbb{Z}$ 의 모든 0이 아닌 원소를 정확히 한 번씩 포함함을 의미한다. 저자들은 이러한 순열이 $n$ 이 짝수일 때만 존재한다는 점에 주목한다. 계산상의 난제는 전체 순열의 수( $n!$ )가 계승적으로 증가하기 때문에, 브루트 포스(brute-force) 방식의 열거가 큰 $n$ 에 대해서는 불가능하다는 점이다.

방법론
저자들은 탐색 공간을 조기에 가지치기(pruning)함으로써 기존의 브루트 포스 접근법보다 크게 개선된 재귀적 백트래킹 알고리즘을 제안한다. 이 방법론은 세 가지 주요 축에 기반한다:

차집합과 시퀀싱(Sequencings) 사이의 전단사(Bijection):
본 논문은 "차집합이 서로 다른 차집합"과 $\mathbb{Z}/n\mathbb{Z}$ 의 "시퀀싱" 사이의 공식적인 전단사 관계(정리 1)를 확립한다. 시퀀싱은 부분 합 $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ 가 모두 서로 다른 순열로 정의된다. 증명 과정은 차집합 $D_\tau = (d_1, \dots, d_{n-1})$ 가 시퀀싱 $\sigma = (0, d_1, \dots, d_{n-1})$ 로 매핑될 수 있고 그 역도 성립함을 보여준다. 이를 통해 저자들은 차집합을 직접 세는 대신 시퀀싱을 세울 수 있다.
곱셈을 통한 대칭 감소(Symmetry Reduction via Multiplication):
보조정리 2를 활용하여, 저자들은 만약 $\sigma$ 가 시퀀싱이고 $r$ 이 $n$ 과 서로소인 정수( $\gcd(r, n) = 1$ )라면, 원소별 곱 $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ 또한 시퀀싱이라는 성질을 이용한다. 이를 통해 알고리즘은 특정 "브랜치"(순열이 $0, 1 $로 시작하는 경우)에 대한 시퀀싱을 계산하고, 각 브랜치를 개별적으로 계산하는 대신 오일러 피 함수$ \phi(n/d)$를 곱하여 다른 브랜치들을 처리할 수 있다.
재귀적 브랜치 가지치기 (알고리즘 2):
새로운 알고리즘의 핵심은 부분 순열을 구축하는 재귀적 탐색이다. 이 알고리즘은 전체 순열을 검증하는 기존의 브루트 포스 방식과 달리, "부분 합(partial sums)"(partials) 상태를 유지한다.

가지치기 로직: 새로운 원소를 부분 순열에 추가했을 때 부분 합이 이미 나타난 값이거나 조기에 0이 되는 경우, 해당 브랜치는 즉시 폐기된다.
효율성: 이는 유효하지 않은 부분 순열을 확장하는 $(n-k)!$ 개의 순열을 탐색하는 것을 방지한다. 예를 들어, $\mathbb{Z}/20\mathbb{Z}$ 에서 부분 순열 $(0, 1, 19)$ 는 인덱스 2에서 부분 합이 0을 생성하며, 이는 유효하지 않다. 알고리즘은 이 전체 브랜치를 버림으로써 검증기에 전달될 뻔한 $17!$ 번의 잠재적 호출을 절약한다.

주요 기여

OEIS A141599의 새로운 항 계산: 개선된 알고리즘을 사용하여 저자들은 $n=20, 22, 24$ $n = 20, 22, 24$ 에 해당하는 수열의 10번째, 11번째, 12번째 항을 계산하였다. 그 값은 다음과 같다:
- $n=20$ : 5,074,931,072
- $n=22$ : 298,557,044,000
- $n=24$ : 21,224,961,132,544
  10번째와 11번째 항은 Bert Dobbelaere에 의해 독립적으로 검증되었다.
이론적 통합: 본 논문은 차집합과 시퀀싱 사이의 전단사 관계에 대한 엄밀한 증명을 제공하여, 고전적 결과(Gilbert, Gordon)와 현재의 계산적 접근법을 통합한다.
알고리즘 최적화: 부분 합 충돌에 기반한 조기 종료 기능을 갖춘 재귀적 브랜치 탐색의 도입은 이 특정 계수 문제에 대해 현재까지 알려진 가장 효율적인 방법이다.

결과 및 데이터 분석
본 논문은 짝수인 $n \le 22$ 에 대해 시퀀싱의 수와 전체 순열( $n!$ )의 수를 비교하는 데이터(표 1 및 2)를 제시한다. 결과에 따르면 시퀀싱과 전체 순열의 비율은 $n$ 이 증가함에 따라 엄격하게 감소하며 급격히 줄어든다. $n=22$ 에서 그 비율은 약 $2.66 \times 10^{-10}$ 이다.

이러한 경험적 증거는 가지치기 전략의 효용성을 뒷받침한다. 유효한 시퀀싱은 전체 순열 공간 내에서 매우 희소하기 때문에, 전체 순열을 생성하고 검증하는 것은 비효리적이다. 유효하지 않은 부분 경로를 즉시 제거하는 재귀적 접근 방식은 관찰된 희소성과 일치한다.

의의 및 주장
저자들은 자신들의 알고리즘이 수열 A141599의 항을 계산하는 데 있어 현재까지 알려진 가장 효율적인 방법이라고 주장한다. 그들은 시간 복잡도가 여전히 초다항식(super-polynomial, 지수 시간보다는 나쁘지만 $O(n!)$ 보다는 나은 수준으로 추정됨)이지만, 가지치기 기술이 유효하지 않은 브랜치에 낭비되는 계산을 피함으로써 브루트 포스 방식보다 "엄격한 개선"을 제공한다고 주장한다.

논문은 향가적인 결론으로, 새로운 수학적 변환을 식별하지 않는 한 계수 알고리즘의 추가적인 개선은 제한적일 것이라고 완곡하게 언급한다. 구체적으로, 그들은 미래의 진전이 (주어진 $n$ 에 대해 작은 시퀀싱 집합을 전체 집합으로 매핑할 수 있는 완전한 변환 집의 식별에 달려 있으며, 이를 통해 전수 조사를 완전히 우회할 수 있을 것임)에 달려 있을 수 있다고 제안한다. 그러나 그들은 이 작업에서 그러한 변환을 제안하지는 않으며, 현재의 재귀적 접근 방식이 정의된 문제를 해결하기 위한 최첨단(state-of-the-art) 방식임을 명시한다.

유사한 논문