🔢 mathematics

Restricted partition functions and additive complements

이 논문은 모든 양의 정수가 적어도 하나의 표현을 갖도록 보장하면서도 다항식 성장을 갖는 제한된 분할 함수를 산출하는 양의 정수의 무한 집합을 구성함으로써, Dai와 Chen의 2016년 질문에 긍정적인 답변을 제시한다.

원저자: Yuchen Ding

게시일 2026-06-17

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Yuchen Ding

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

당신에게 아주 특별한 블록들이 가득 담긴 거대하고 무한한 도구 상자가 있다고 상상해 보세요. 각 블록은 집합 A라고 불리는 리스트의 숫자에 의해 결정되는 특정 크기를 가지고 있습니다. 또한 당신에게는 각 블록을 몇 개나 사용할 수 있는지 알려주는 집합 M이라는 특별한 규칙책이 있습니다.

이 논문의 수학자인 위천 딩(Yuchen Ding)은 매우 구체적인 질문을 던지고 있습니다: 우리가 이 두 리스트(A와 M)를 설계하여, 모든 양의 정수(1, 2, 3 등)를 만들 수 있으면서도, 그 만드는 방법의 수가 통제 불능 상태로 늘어나지 않도록 할 수 있을까?

다음은 일상적인 비유를 사용한 개념 설명입니다:

1. 건축 블록 (제한된 분할)

숫자 $n$ (예: 100)을 당신이 만들고자 하는 탑이라고 생각해 보세요.

집합 A는 사용 가능한 블록 크기의 목록입니다 (예: 1, 4, 16, 256...).
집합 M은 "배수"에 대한 규칙책입니다. 이 규칙은 "4짜리 블록은 0개, 1개 또는 2개를 사용할 수 있지만, 16짜리 블록은 0개, 5개 또는 10개를 사용할 수 있다"라고 말합니다.
목표: 당신은 이 규칙들을 사용하여 모든 숫자 $n$ 을 만들 수 있어야 합니다.
문제: 만약 같은 숫자를 만드는 방법이 너무 많아지면, 수학적으로 매우 복잡해집니다. 저자는 어떤 숫자( $p$ )를 만드는 방법의 수가 완만하게 증가하기를 원합니다. 구체적으로는 "다항식 성장(polynomial growth)"을 의미합니다.

비유: 당신이 쿠키를 굽고 있다고 상상해 보세요.

만약 초코칩 쿠키를 만드는 레시피가 100가지라면, 그것을 모두 관리하기란 매우 힘든 일입니다.
"다항식 성장"이란, 당신이 점점 더 큰 배치의 쿠키를 구우려고 할 때, 새롭고 독특한 레시피를 발견하는 수가 순식간에 수백만 개로 폭발하며 늘어나는 것이 아니라, 관리 가능하고 예측 가능한 속도로 늘어남을 의미합니다.

2. "간격(Gap)" 문제

이 논문 이전에도, 수학자들은 모든 숫자를 만들 수 있는 리스트를 만드는 법을 알고 있었지만, 그 블록들의 크기 사이의 "간격"이 아주 크지는 않았습니다.

질문: 블록들이 엄청나게 빠르게 커지는 리스트를 만들 수 있을까요? 예를 들어 첫 번째 블록은 크기가 1이고, 다음은 100, 그다음은 10,000, 그리고 그다음은 1,000,000인 리스트를 상상해 보세요.
이 숫자들 사이의 간격은 너무 넓어서, 보통은 수학적 체계가 무너지거나 모든 숫자를 만드는 것이 불가능해지거나, 혹은 만드는 방법의 수가 폭발적으로 늘어나게 됩니다.

3. 해결책: "완벽한 쌍"

딩은 답이 YES라고 증명합니다. 당신은 이러한 거대한 간격을 가지면서도 모든 숫자를 만들 수 있는 리스트를 만들 수 있습니다.

그는 **가법적 보수(Additive Complements)**라는 기발한 트릭을 도입하여 이를 수행합니다.

비유: 두 팀, 팀 B와 팀 S가 있다고 상상해 보세요.
- 팀 B의 구성원들은 2의 거듭제곱(1, 2, 4, 8, 16...)들입니다.
- 팀 S는 팀 B가 남긴 "구멍"을 채워주는 특별한 숫자 그룹입니다.
- 함께라면, 팀 B에서 한 명과 팀 S에서 한 명을 뽑아 그들의 "값"을 더함으로써, 수직선 위의 모든 숫자를 형성할 수 있습니다. 그들은 서로 "보수" 관계입니다.

딩은 수학자 루사(Ruzsa)의 유명한 결과를 사용하여, 팀 S가 흥미로울 만큼 충분히 희소하면서도 구멍을 메울 수 있을 만큼 충분히 밀도가 높도록 찾아냅니다.

4. 구성 방식

딩은 이 두 마법의 리스트, A와 M을 이 팀들을 기반으로 만듭니다:

집합 A (블록): 그는 팀 B의 숫자들을 2의 거듭제곱(예: $2^1, 2^2, 2^4, 2^8...$ )으로 바꿉니다. 이를 통해 질문에서 요구하는 "거대한 간격"을 만들어냅니다.
집합 M (규칙): 그는 팀 S를 기반으로 규칙을 만듭니다. 이 규칙은 팀 S의 작은 조각들을 조합하여 계수(즉, "몇 개를 사용할지" 부분)를 형성할 수 있게 해줍니다.

마법 같은 점: 팀 B와 팀 S가 완벽한 보수 관계이기 때문에, 당신은 언제나 어떤 숫자든 이 특정 규칙에 맞는 합으로 분해할 수 있습니다. 팀 S가 정교하게 선택되었기 때문에, 이를 만드는 방법의 수가 폭발하지 않고 "다항식" 한계 내에 머물게 됩니다.

5. 이것이 왜 중요한가 (논문에 따르면)

이 논문은 2016년 다이(Dai)와 첸(Chen)이 제기한 특정 질문에 답합니다.

질문: "블록들이 무한히 멀리 떨어져 있음에도 불구하고, 우리가 모든 숫자를 관리 가능한 조합으로 만들 수 있는 두 개의 무한 집합이 존재하는가?"
답변: 그렇습니다. 딩은 블록들의 로그 값의 비율이 무한대로 발산할 정도로 간격이 매우 빠르게 커지는 구체적인 사례를 구축했습니다.

"AI" 요소에 대한 참고 사항

저자 위천 딩은 연구 과정에서 AI 도구(ChatGPT)를 사용했음을 공개적으로 밝히고 있습니다.

AI가 한 일: 2의 거듭제곱과 관련된 집합을 살펴보도록 제안하고, "틈새가 있는 수열(lacunary sequences)"에 관한 루사의 특정 정리를 안내했습니다.
저자가 한 일: 저자는 수학적 내용을 검증하고, 논리를 확인하며, 증명을 재구성하고, 최종 논문을 작성했습니다. 그는 작업의 정확성에 대해 전적인 책임을 집니다.

요약

위천 딩은 숫자 만들기 퍼즐을 풀었습니다. 그는 블록들이 (사다리의 가로대처럼) 엄청나게 멀리 떨어져 있는 경우에도, 특정하고 관리 가능한 일련의 기술을 사용한다면:

모든 정수를 만들 수 있고,
그것을 만드는 방법의 수가 통제 불능 상태로 늘어나지 않는다는 것을 보여주었습니다.

이는 마치 사다리의 가로대 간격이 1마일씩 떨어져 있더라도, 특정한 관리 가능한 등반 기술을 사용한다면 부드럽게 올라갈 수 있다는 것을 증명하는 것과 같습니다.

기술 요약: 제한된 분할 함수와 가법적 보수

문제 정의
본 논문은 제한된 분할 함수에 관한 가법 정수론의 특정 질문을 다룬다. $\mathbb{N}$ 을 양의 정수 집합, $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ 라 하자. 부분 집합 $A, M \subseteq \mathbb{N}$ 에 대하여, 제한된 분할 함수 $p(n, A, M)$ 은 다음과 같은 형태의 정수 $n$ 의 표현 개수를 센다:
$n = \sum_{a \in A} m_a a$
여기서 $m_a \in M \cup \{0\}$ 이며, 모든 $a \in A$ 에 대해 유한한 수의 $m_a$ 만이 0이 아니다. 함수 $p$ 는 상수 $c > 0$ 와 $n_0$ 가 존재하여 모든 $n \geq n_0$ 에 대해 $p(n, A, M) \leq n^c$ 를 만족할 때 *다항식 성장(polynomial growth)*을 갖는다고 한다.

Dai와 Chen(2016)이 제기한 핵심 문제(질문 1)는 다음을 만족하는 양의 정수 두 무한 집합 $A = \{a_n\}_{n=1}^\infty$ 와 $M$ 이 존재하는가 하는 것이다:

집합 $A$ 는 매우 희소하며, $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ 를 만족한다.
모든 충분히 큰 $n$ 에 대해 $p(n, A, M) > 0$ 이다 (즉, 모든 큰 정수는 표현 가능하다).
분할 함수 $p(n, A, M)$ 은 다항식 성장을 보인다.

Alon(2012)과 Dai 및 Chen(2016)의 선행 연구들은 덜 엄격한 희소성 조건이나 특정 지수 경계(예: $p(n) < n^{2+o(1)}$ ) 하에서 이러한 집합들의 존재성을 입증하였으나, 초로그(super-logarithmic) 희소성의 경우는 미해결 상태로 남아 있었다.

방법론
저자 Yuchen Ding는 **가법적 보수(additive complements)**와 **이진 전개(binary expansions)**에 기반한 구성을 사용한다. 핵심 전략은 다음과 같다:

가법적 보수의 정의: 두 집합 $B, S \subseteq \mathbb{N}_0$ 가 완전 가법적 보수라는 것은 $B + S = \mathbb{N}_0$ 임을 의미한다.
집합 $A$ 와 $M$ 의 구성: 본 논문은 특정 계수 조건을 만족하는 한 쌍의 가법적 보수 $B$ $B$ 와 $S$ $S$ 를 바탕으로 $A$ $A$ 와 $M$ $M$ 을 구성한다. 구체적으로:
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (집합 $S$ 의 거듭제곱들의 유한 부분 합)
단사 사상(Injective Mapping): 증명 과정은 $p(n, A, M)$ 에 의해 계산되는 표현들을 곱 공간 $S \times B$ 의 유한 부분 집합들로의 단사 사상으로 연결한다. 이진 전개의 유일성을 활용하여, 저자는 $n$ 의 임의의 표현이 $s+b \leq \log_2 n$ 을 만족하는 쌍 $(s, b)$ 의 집합에 대응함을 보여준다.
성장률 경계 설정: 이러한 표현의 개수는 $s+b \leq N$ (여기서 $N \approx \log_2 n$ )을 만족하는 쌍 $(s, b) \in S \times B$ 의 개수로 제한된다. 이 계수는 $S(N)B(N)$ 에 의해 유계임이 밝혀졌다. 만약 $B(x)S(x) \ll x$ 라면, 결과적인 분할 함수는 다항식 성장을 갖는다.

주요 기여 및 결과
본 논문은 다음의 결과들을 통해 Dai와 Chen의 질문 1에 대해 긍정적인 답변을 제공한다:

정리 1: $B$ 와 $S$ 가 계수 조건 $B(x)S(x) \ll x$ 를 만족하는 완전 가법적 보수라고 하자. $A$ 와 $M$ 이 위와 같이 정의될 때, 모든 $n \in \mathbb{N}$ 에 대해 $p(n, A, M) > 0$ 이며 $p(n, A, M)$ 은 다항식 성장을 갖는다.
따름정리 1 (질문 1의 해결): 2의 거듭제곱의 가법적 보수에 관한 Ruzsa(1972)의 결과를 인용하여, 저자는 정리 1의 조건을 만족하는 특정한 집합 $A$ $A$ 와 $M$ $M$ 을 구성한다.
- $B = \{0\} \cup \{2^k : k \geq 0\}$ 라 하자.
- $S$ 는 $S(x) \ll x / \log x$ 를 만족하고 $B+S = \mathbb{N}_0$ 를 만족하는(유한한 원소를 추가한 후) Ruzsa의 정리로부터 유도된 $\mathbb{N}$ 의 부분 집합이다.
- 결과적으로 생성된 집합 $A$ 의 원소는 $n \geq 2$ 에 대해 $a_n = 2^{2^{n-2}}$ 이다.
- 이 구성은 $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ 를 만족하여 극단적인 희소성 요구 조건을 충족한다.
- $B(x) \ll \log x$ 이고 $S(x) \ll x / \log x$ 이므로, 곱 $B(x)S(x) \ll x$ 가 성립하며, 이는 $p(n, A, M)$ 의 다항식 성장을 보장한다.

의의
본 논문은 Dai와 Chen의 2016년 질문에 대해 긍정적인 답을 내놓았다고 주장한다. 이는 허용된 부분들의 집합 $A$ 가 (이전 사례들보다 훨씬 더 희소하여) 로그의 거듭제곱보다 빠르게 증가하는 간격을 가짐에도 불구하고, 제한된 분할 함수가 전사적(모든 양의 정수를 표현)이면서 동시에 다항식 성장을 가질 수 있음을 입증한다.

본 연구는 제한된 분할 함수의 성장률을 가법적 보수의 계수 특성과 직접 연결함으로써 기존 연구를 일반화한다. 저자는 이 구성이 초기 단계에서 생성형 AI(ChatGPT)의 도움을 받아 탐색되었으며, AI가 집합의 특정 형태와 Ruzsa의 정리와의 연결 고리를 제안했으나, 수학적 검증, 재구성 및 최종 증명은 저자의 독립적인 작업임을 밝히고 있다.