Construction of codes over a commutative non-unital ring from simplicial complexes and their applications

기술 요약: 심플리셜 복합체로부터의 가환 비단위 환(Commutative Non-Unital Ring) 상의 부호 구축 및 그 응용

문제 정의 및 배경
본 논문은 유한 환(finite ring) 상의 선형 부호, 특히 차수가 $p^2$인 가환 비단위 환 $I$와 그 확장 $S$에 초점을 맞추어 연구한다. 유한 체와 단위 환 상의 선형 부호는 이미 잘 확립되어 있으나, 비단위 환 상의 부호 연구는 보다 최근의 발전이다. 기존 연구들은 비가환 환 $E$(차수 $p^2$)를 포함한 비단위 환 상의 준 자기 쌍대(quasi self-dual) 및 자기 직교(self-orthogonal) 부호를 탐구해 왔다. 본 연구는 이러한 조사를 가환 비단위 환 $I$와 그 확장 $S$로 확장하여, 심플리셜 복합체로부터 유도된 정의 집합(defining sets)을 사용하여 최적의 파라미터를 갖는 부호를 구축하는 것을 목표로 한다. 주요 목표는 이 부호들의 가중치 분포, 최소성(minimality), 최적성을 결정하고, 비밀 공유 스킴(secret-sharing schemes), 국소 복구 가능 부호(locally recoverable codes, LRCs), 그리고 강하게 정규 그래프(strongly regular graphs)의 구축에 대한 응용을 탐구하는 것이다.

방법론
저자들은 심플리셜 복합체를 사용하여 환 $S$ 상의 선형 부호를 구축하기 위해 **정의 집합 방법(defining set method)**을 채택한다.

1. 환 구조: 환 $S$는 가환 비단위 환 $I = \langle a, b \mid pa=0, pb=0, a^2=b, ab=0 \rangle$의 확장으로 정의된다. $S$의 원소들은 $s, t \in \mathbb{F}_q$ ($q=p^r$)에 대하여 $as + bt$ 형태를 가진다.
2. 부호 구축: 순서가 있는 멀티셋(ordered multiset) $D \subseteq S^m$을 정의 집합으로 사용하여 $S$ 상의 선형 부호 $C_D$를 다음과 같이 정의한다:
   $$C_D = \{ (v \cdot d)_{d \in D} : v \in S^m \}$$
   여기서 곱 $v \cdot d$는 환의 곱셈 규칙을 통해 정의된다.
3. 심플리셜 복합체(Simplicial Complexes): 정의 집합 $D$는 $\mathbb{F}_q^m$ 상의 심플리셜 복합체 $\Delta$를 사용하여 구축된다. 구체적으로, 저자들은 $D = a\Delta_1 + b\Delta_2$ 형태의 집합을 고려하며, 여기서 $\Delta_1$과 $\Delta_2$는 (잠재적으로 여러 개의 극대 원소를 가진) 심플리셜 복합체 및 그 여집합이다.
4. 가중치 분석:
   • 리 가중치(Lee Weight): 부호어(codeword)의 리 가중치는 그레이 맵(Gray map) $\Phi: S \to \mathbb{F}_q^2$ (단, $\Phi(as+bt) = (t, s+t)$)를 사용하여 분석된다. 리 가중치는 그레이 이미지의 해밍 가중치(Hamming weight)로 계산된다.
   • 부분체 유사 부호(Subfield-like Codes): $\tau(C_D)$와 같은 부분체 유사 부호를 구성하기 위해 투영 사상 $\tau: S \to \mathbb{F}_q$ ($\tau(as+bt) = t$)를 사용한다.
5. 분석 도구: 저자들은 가중치 분포와 파라미터를 명시적으로 도출하기 위해 캐릭터 합(character sums), 포함-배제의 원리, 그리고 심플리셜 복합체의 성질(특히 극대 원소 및 그 교집합)을 활용한다.

주요 기여 및 결과

1. 명시적 가중치 분포 및 파라미터:
   본 논문은 심플리셜 복합체와 그 여집합의 조합으로 형성된 정의 집합에 대한 $S$-선형 부호의 리 가중치 분포를 결정한다. 다섯 가지의 서로 다른 정의 집합 케이스($D = a\Delta_1 + b\Delta_2$, $a\Delta_1 + b\Delta_2^c$ 등)가 분석된다.

   • $S$-선형 부호의 파라미터(길이, 크기, 최소 리 거리)가 확립된다.
   • 그레이 이미지 $\Phi(C_D)$와 부분체 유사 부호 $\tau(C_D)$가 $\mathbb{F}_q$ 상의 선형 부호임을 보여준다.
   • 심플리셜 복합체가 단일 극대 원소를 갖는 경우에 대한 명시적인 가중치 분포를 제공하며, 이를 통해 생성된 많은 부호들이 few-weight(구체적으로 1-weight 또는 2-weight)이자 divisible임을 밝힌다.

2. 최소성 및 최적성:

   • 최소성(Minimality): 그레이 이미지 부호와 부분체 유사 부호가 최소성을 갖기 위한 충분 조건을 확립한다. 부호가 최소하다는 것은 모든 0이 아닌 부호어가 오직 자신의 스칼라 배만을 포함함을 의미한다. 저자들은 심플리셜 복합체의 극대 원소의 크기와 필드 크기 $q$ 사이의 관계를 포함하는 부등식을 도출하여 최소성을 보장한다.
   • 최적성(Optimality): 이 부호들이 그리스머 경계(Griesmer bound)에 대해 최적인지를 조사한다. 여러 부호 군이 파라미터 $m, |M|, |N|, q$에 대한 특정 조건 하에서 최적임을 보여준다.

3. 자기 직교성(Self-Orthogonality):
   그레이 이미지 부호와 부분체 유사 부호가 유클리드(Euclidean) 또는 헤르미션(Hermitian) 자기 직교가 되기 위한 조건을 제공한다. 이 조건들은 부호어 가중치의 가해성(divisibility)과 $q$의 특정 값(예: $q=2, 3, 4$)에 의존한다.

4. 응용:

   • 국소 복구 가능 부호(LRCs): 저자들은 심플리셜 복합체의 0이 아닌 원소들과 관련된 특정 정의 집합을 선택함으로써, 국소도(locality) 2와 3을 갖는 LRC 군을 구축한다. 이 부호들은 부분체 유사 부호 $\tau(C_D)$로부터 유도된다.
   • 비밀 공유 스킴(SSS): 구축된 최소 부호의 쌍대(dual)를 기반으로 한 비밀 공유 스킴의 최소 접근 구조(minimal access structures)를 결정한다. 논문은 최소 접근 집합의 수와 각 참여자의 참여 빈도를 명시한다.
   • 강하게 정규 그래프(SRGs): 투영 2-가중 부호(projective two-weight codes)와 SRG 사이의 대응 관계를 활용하여, 여러 계열의 강하게 정규 케일리 그래프(Cayley graphs)를 구축한다. 이 그래프들의 파라미터 $(N, K, \lambda, \mu)$를 명시적으로 결정한다. 또한, 이 SRG들의 보그래프(complement graphs) 역시 강하게 정규 그래프임을 보이고 그 파라미터를 계산한다.

의의 및 주장
본 논문은 심플리셜 복합체 접근법을 가환 비단위 환 $I$와 그 확장 $S$에 성공적으로 적용함으로써 비단위 환 상의 부호 이론을 진전시켰다고 주장한다. 본 연구의 의의는 다음과 같다:

• 그레이 이미지 및 부분체 유사 구성을 통해 유한 체 상의 새로운 가해성(divisible) 및 few-weight 부호 군을 생성한다.
• 이 부호들이 최소성, 최적성 및 자기 직교성을 갖기 위한 명시적인 기준을 제공하며, 이는 암호학 및 조합론적 응용에 필수적이다.
• 구축된 부호의 다양성을 입증하여, 분산 저장에 중요한 국소 복구 가능 부호(LRCs) 및 **비밀 공유 스킴(SSS)**에 적합한 부호를 생성한다.
• 이 대수적 구축과 강하게 정규 그래프(SRGs) 사이의 직접적인 연결 고리를 확립하여, 부호 이론적 원리로부터 특정 파라미터를 가진 SRG를 생성하는 방법을 제시한다.

본 연구는 구축된 부호의 범위와 그 즉각적인 응용을 넘어선 실험적 구현이나 미래의 이론적 확장을 제안하지 않는다. 연구의 초점은 파라미터의 대수적 도출과 확립된 부호 이론 프레임워크 내에서의 속성 검증에 맞춰져 있다.