On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

기술적 요약: 리드-뮬러 부분코드, 그라스마니안 분할 및 합-무함수

문제 진술
본 논문은 코딩 이론과 유한 기하학의 세 가지 상호 연결된 문제를 다룹니다:

1. 리드-뮬러 부분코드: 리드-뮬러 코드 $RM(r, n)$의 모든 최소 가중치 코드워드를 피하는 선형 부분코드를 구성하여, 부모 코드의 최소 거리보다 엄격하게 큰 최소 거리를 달성합니다.
2. 합-무함수의 존재성: $k$-차 합-무함수 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$의 존재 조건과 필요한 하한을 결정합니다. 함수가 $k$-차 합-무함수라는 것은 임의의 $k$-차원 아핀 부분공간에 대한 함수 값의 합이 0 이 아니라는 것을 의미합니다. Carlet 이 최근 이 개념을 도입하고 그러한 함수들의 무한한 계열 (여기서 $m=n$) 을 제공했지만, $m < n$인 경우와 특정 차수 $k \ge 3$에 대한 그러한 함수의 존재성은 여전히 대부분 미해결 상태입니다.
3. 그라스마니안 분할: $\mathbb{F}_2^n$의 모든 $k$-차원 선형 부분공간 (그라스마니안) 의 집합을 상수-차원 부분공간 코드로 분할하는 문제입니다. 이는 꼭짓점이 $k$-공간이고 간선이 $k-1$차원에서 교차하는 공간들을 연결하는 그라스만 그래프의 색칠수 $\chi(J_2(n, k))$를 결정하는 것과 동치입니다.

방법론
저자들은 코딩 이론과 합-무함수의 성질 사이의 엄밀한 대응 관계를 확립합니다.

• 대응 구성: 본 논문은 비퇴화 $(n-r)$-차 합-무함수 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$가 코디멘션 $m$이고 최소 거리 $3 \cdot 2^{n-r-1}$을 갖는 $RM(r, n)$의 선형 부분코드 존재와 동치임을 증명합니다. 이는 함수$F$의 평가 벡터를 사용하여 부분코드에 대한 패리티-체크 행렬을 구성함으로써 달성됩니다.
• 대수적 분석: 저자들은 부울 함수의 대수적 차수, 고계 도함수의 성질, 그리고 리드-뮬러 코드의 구조 (특히 평면과 그들의 대칭 차이를 통한 최소 및 차수-최소 가중치 코드워드의 특성화) 를 활용하여 합-무함수의 존재에 대한 필요 조건을 유도합니다.
• 함수를 통한 그래프 색칠: 본 논문은 "증거 함수" $\omega_F(A) = \sum_{x \in A} F(x)$를 사용하여 그라스만 그래프에 대한 색칠을 정의합니다. 인접한 꼭짓점 ($k-1$차원에서 교차하는 부분공간) 이 서로 다른 0 이 아닌 값으로 매핑되도록 보장함으로써, 저자들은 유효한 색칠을 구성합니다.
• 계산적 검증: 작은 차원 ($n=5, 6, 7$) 에 대해 저자들은 알려진 거의 완벽한 비선형 (APN) 함수들 사이에서 다차수 합-무함수 (여러 차수 $k$에 대해 합-무인 함수) 의 존재를 검증하기 위해 계산적 탐색을 수행합니다.

주요 기여 및 결과

1. 동치 정리 (정리 1.1):
   본 논문은 다음과 같은 전단사 대응을 확립합니다: 비퇴화 $(n-r)$-차 합-무 $(n, m)$-함수가 존재할 필요충분조건은 최소 거리 $3 \cdot 2^{n-r-1}$을 갖는 $RM(r, n)$의 코디멘션$m$ 선형 부분코드가 존재하는 것입니다.

   • 의의: 이는 $RM(r, n)$의 모든 최소 가중치 코드워드를 피하는 새로운 리드-뮬러 부분코드 계열을 산출합니다. 이러한 부분코드들은 원래 코드의 최소 거리의 1.5 배인 최소 거리를 가지며, 코디멘션은 단지$n$입니다. 범위$2 < r < n-2$에 대해 이러한 코드들은 새로운 것으로 보입니다.

2. $m$에 대한 새로운 하한 (정리 3.5):
   저자들은 $k$-차 합-무함수의 존재를 위한 출력 차원 $m$에 대한 첫 번째 비자명한 하한을 유도합니다. $2 \le k \le n-2$에 대해, $(n, m)$-함수가 $k$-차 합-무라면 다음이 성립합니다:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   이 결과는 $m < n$인 경우, 특정 $k$ 범위에 대해 그러한 함수가 존재할 수 없음을 의미하며, 이는 $m=n$인 경우로 제한되었던 이전 지식을 정교화합니다.

3. 알려진 계열의 비퇴화성 (정리 3.6):
   본 논문은 Carlet 이 도입한 멱함수 계열 $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$이 $k < n$인 경우 비퇴화임을 증명합니다. 이는 이러한 함수들이 진정으로 전체 출력 공간 차원 $n$을 필요로 하며, 합-무 성질을 유지하면서 저차원 함수로 축소될 수 없음을 확인해 줍니다.

4. 개선된 그라스만 그래프 색칠 (정리 5.1):
   저자들은 이전의 색칠 결과를 일반화합니다. 대수적 차수가 $k$인 함수 $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$가 $(k-1)$-차 및 $k$-차 합-무함수라면, 그라스만 그래프 $J_2(n+1, k)$는 $\binom{m}{1}_2 = 2^m - 1$개의 색으로 유효한 색칠을 허용함을 보입니다.

   • 응용: 홀수 차원에서의 역함수 (이는 $\{1, 2, n-2, n-1\}$-차 합-무함수임) 를 사용하여, 저자들은 $J_2(n+1, n-1)$에 대한 색칠을 유도합니다.
   • 구체적 결과: $n=5$의 경우, 3 차 $\{2, 3\}$-차 합-무함수 ($x^7$ 및 $x^{21}$) 의 존재는 $\chi(J_2(6, 3)) \le 31$이라는 하한을 이끌어내어, 이전에 알려진 상한을 개선합니다.

5. 다차수 함수에 대한 계산적 발견:
   본 논문은 $n=6$의 경우 알려진 APN 함수 중 어느 것도 3 차 또는 4 차 합-무가 아니라고 보고합니다. $n=7$의 경우, Gold APN 함수 ($x^{15}, x^{77}, x^{85}$) 와 동치인 함수들만이 4 차 합-무인 것으로 발견되었습니다. 이는 다차수 합-무함수가 희귀하며 구성하기 어렵다는 것을 시사합니다.

의의 및 주장
본 논문은 $k$-차 합-무함수와 향상된 최소 거리를 갖는 리드-뮬러 부분코드 구성 사이의 직접적인 연결을 확립한 최초의 연구라고 주장합니다. 이 연결은 최소 가중치 코드워드를 피하는 부분코드를 생성하기 위한 새로운 대수적 도구를 제공합니다.

또한, 이 작업은 $m < n$인 합-무함수의 존재에 대한 첫 번째 비자명한 필요 조건을 제공하여 Carlet 이 제기한 특정 미해결 문제를 해결합니다. 이러한 함수들을 그라스만 그래프의 색칠수와 연결함으로써, 본 논문은 특히 $k > 2$인 경우에 $\chi(J_2(n, k))$에 대한 상한을 개선하는 방법을 제시합니다.

저자들은 새로운 합-무함수 구성에 대해서는 겸손한 태도를 유지하며, 알려진 멱함수들을 넘어 진정으로 새로운 예시를 구성하는 것이 여전히 어렵다고 지적합니다. 그들은 $k \ge 3$에 대한 다차수 합-무함수의 존재를 코딩 이론 (비선형 코드) 과 그래프 이론 모두에 함의를 가진 중요한 미해결 문제로 제시합니다.