# S₄ Group Analysis — Orbit Classification of Boolean Function Spaces

**버전:** 1.2  
**작성일:** 2026-06-23  
**최종 갱신:** 2026-06-23 (OC-1~OC-5 완료 — Space(NOT) 32궤도, L∩M 3궤도 신규 확인)  
**위치:** `6BooleanFunctionSpaceTheory/theory/S4GroupAnalysis.md`  
**관련 TODO 항목:** `FutureWorks.md §1 (우선순위 1)`, `IntegrationMap.md §2.1`  
**관련 문서:** `theory/FunctionSpaceTheory.md`, `questions/OQ2_axisswap_symmetry.md`, `fq/FQ_B_kmap_geometry.md §FQ-9`  
**목적:** Repo 3 (변수 재배열 불변성) ↔ Repo 6 (게이트 공간 이론)의 군론적 통합

---

## 0. 이 문서의 위치

`FutureWorks.md` §1은 S₄ 군론적 분류를 **연구 우선순위 1번**으로 명시했다:

> "S₄ 궤도 분류 — Repo 3·6 통합의 직접적 수학적 성과"

또한 `IntegrationMap.md §2.1`은 다음 두 작업을 **우선순위 높음**으로 표시했다:
- Space(AND)의 S₄ 궤도 분류 (단조 함수 168개)
- S₄ 불동점 완전 분류

이 문서는 해당 분석의 수학적 토대를 구축한다.

---

## 1. 수학적 프레임워크

### 1.1 S₄의 4변수 Boolean 함수에 대한 작용

**군:** S₄ = 4개 원소 {A, B, C, D}의 모든 순열의 군 (크기 24)

**작용:** 순열 σ ∈ S₄를 4변수 Boolean 함수 f에 적용:
$$(\sigma \cdot f)(A, B, C, D) = f(\sigma^{-1}(A), \sigma^{-1}(B), \sigma^{-1}(C), \sigma^{-1}(D))$$

또는 등가로: $(f \circ \sigma)(x) = f(\sigma(x))$

### 1.2 핵심 명제: Space(G)는 S₄-불변

**명제 1.1:** 임의의 게이트 G에 대해, Space(G)는 S₄ 작용 하에 닫혀 있다.

즉, $f \in \text{Space}(G)$ 이고 $\sigma \in S_4$ 이면 $f \circ \sigma \in \text{Space}(G)$.

**증명 스케치:**  
f가 G-게이트만으로 구현되는 회로를 가진다면, f∘σ는 같은 회로에서 입력 와이어를 σ에 따라 재배치한 것이다. 회로의 게이트 종류(G)는 변하지 않으므로 f∘σ ∈ Space(G). ∎

**결론:** 각 Space(G)는 S₄ 궤도들의 합집합으로 분해된다.

### 1.3 S₄의 켤레류(Conjugacy Classes)

Burnside의 보조정리 적용을 위해 S₄의 켤레류(= 원소 개수 동일):

| 켤레류 (치환 타입) | 원소 수 | 예시 |
|----------------|--------|-----|
| 항등원 | 1 | (A)(B)(C)(D) |
| 호환(transposition) | 6 | (AB), (AC), (AD), (BC), (BD), (CD) |
| 3-순환(3-cycle) | 8 | (ABC), (ABD), (ACD), (BCD), 그 역원들 |
| 4-순환(4-cycle) | 6 | (ABCD), (ABDC), (ACBD), 그 역원들 |
| 이중 호환 | 3 | (AB)(CD), (AC)(BD), (AD)(BC) |
| **합계** | **24** | |

### 1.4 Burnside의 보조정리

$$|\text{Orbits}| = \frac{1}{|S_4|} \sum_{\sigma \in S_4} |\text{Fix}(\sigma, \text{Space}(G))|$$

여기서 $\text{Fix}(\sigma, \text{Space}(G)) = \{ f \in \text{Space}(G) : f \circ \sigma = f \}$.

### 1.5 카르노 맵의 토러스 위상과 시각적 패턴 해석 주의사항

4변수 카르노 맵은 평면이 아니라 **환면체(Torus)** 위에 놓인 구조이다:
- **상하 연결:** AB=00 행과 AB=10 행은 인접한다 (Gray 코드에서 00과 10은 한 비트 차이)
- **좌우 연결:** CD=00 열과 CD=10 열은 인접한다 (동일 이유)

> **⚠️ 중요 귀결:** 카르노 맵의 시각적 패턴을 기술할 때 "좌상단", "우하단", "모서리" 등 절대적 위치 표현은 **토러스 위상 하에서 의미가 없다.** 어떤 셀도 다른 셀보다 특별히 "끝"이나 "모서리"에 있지 않으며, 특정 패턴이 맵의 어느 위치에 나타나는지는 오직 **변수 명명·배열 순서**에만 의존한다.

| 잘못된 기술 (위치 의존) | 올바른 기술 (토러스 불변) |
|----------------------|---------------------|
| "좌상단 한 칸만 흰색" | "HW=0인 유일한 셀(m0) 하나만 0" |
| "우하단에 집중된 패턴" | "HW≥3인 셀들만 1" |
| "우하단 한 칸만 채워짐" | "HW=4인 유일한 셀(m15) 하나만 1" |

이 위상적 사실은 S₄ 궤도 분류와 직접 연결된다: **같은 궤도의 함수들은 카르노 맵에서 서로 "토러스 회전·반사 대칭"인 패턴을 가진다.** 따라서 패턴의 시각적 위치가 다르더라도 위상적으로 동치인 경우, 같은 궤도의 원소로 처리해야 한다.

---

## 2. Space(XOR) = L (아핀 클론)의 완전 분석

### 2.1 아핀 함수의 구조

4변수 아핀 함수 (= Space(XOR)의 원소):
$$f(A, B, C, D) = a_0 \oplus a_1 A \oplus a_2 B \oplus a_3 C \oplus a_4 D, \quad a_i \in \{0, 1\}$$

총 원소 수: $2^5 = 32$개 (계수 벡터 $(a_0, a_1, a_2, a_3, a_4) \in \{0,1\}^5$).

### 2.2 S₄ 작용이 아핀 계수에 미치는 효과

σ = (AB)인 경우:
$$f \circ (AB)(A,B,C,D) = f(B,A,C,D) = a_0 \oplus a_1 B \oplus a_2 A \oplus a_3 C \oplus a_4 D$$

$f \circ (AB) = f$ 조건: $a_1 = a_2$ (A와 B의 계수가 같아야 함).

**일반 원리:** 순열 σ가 변수 xᵢ와 xⱼ를 교환하면, 불동점 조건은 $a_i = a_j$.

### 2.3 각 켤레류별 Fix(σ, L) 계산

**원리:** σ의 각 궤도(σ의 작용 하에 같은 궤도에 속하는 변수 인덱스 집합)에 대해, 해당 계수들은 같아야 한다.

| 켤레류 | σ의 궤도 구조 | 자유 계수 수 | Fix(σ, L) |
|------|------------|----------|----------|
| 항등원 (A)(B)(C)(D) | 4개 1-궤도 | $a_0, a_1, a_2, a_3, a_4$ → 5개 | $2^5 = 32$ |
| 호환 (AB)(C)(D) | {A,B} 1개 + {C} 1개 + {D} 1개 | $a_0, a_1(=a_2), a_3, a_4$ → 4개 | $2^4 = 16$ |
| 3-순환 (ABC)(D) | {A,B,C} 1개 + {D} 1개 | $a_0, a_1(=a_2=a_3), a_4$ → 3개 | $2^3 = 8$ |
| 4-순환 (ABCD) | {A,B,C,D} 1개 | $a_0, a_1(=a_2=a_3=a_4)$ → 2개 | $2^2 = 4$ |
| 이중 호환 (AB)(CD) | {A,B} + {C,D} → 2개 2-궤도 | $a_0, a_1(=a_2), a_3(=a_4)$ → 3개 | $2^3 = 8$ |

### 2.4 Burnside 적용 (Space(XOR))

$$|\text{Orbits}(S_4, L)| = \frac{1}{24}(1 \times 32 + 6 \times 16 + 8 \times 8 + 6 \times 4 + 3 \times 8)$$
$$= \frac{1}{24}(32 + 96 + 64 + 24 + 24) = \frac{240}{24} = \mathbf{10}$$

**Space(XOR)는 S₄ 작용 하에 정확히 10개의 궤도를 가진다.** ✓

### 2.5 10개 궤도의 완전 열거

궤도는 "XOR에 포함된 변수 개수"와 "상수 항 $a_0$의 값"으로 분류된다:

| 궤도 | 대표 함수 | 궤도 크기 | 의미 |
|-----|---------|---------|-----|
| O₁ | $0$ | 1 | 상수 0 |
| O₂ | $1$ | 1 | 상수 1 |
| O₃ | $A$ | 4 | 단일 변수 투영 |
| O₄ | $A \oplus 1$ | 4 | 단일 변수 투영의 보수 |
| O₅ | $A \oplus B$ | 6 | 2변수 XOR |
| O₆ | $A \oplus B \oplus 1$ | 6 | 2변수 XOR의 보수 |
| O₇ | $A \oplus B \oplus C$ | 4 | 3변수 XOR |
| O₈ | $A \oplus B \oplus C \oplus 1$ | 4 | 3변수 XOR의 보수 |
| O₉ | $A \oplus B \oplus C \oplus D$ | 1 | 완전 패리티 (체커보드) |
| O₁₀ | $A \oplus B \oplus C \oplus D \oplus 1$ | 1 | 체커보드의 보수 |

**검증:** $1+1+4+4+6+6+4+4+1+1 = 32$ ✓

### 2.6 Space(XOR)의 S₄-불동점 (Fixed Points)

S₄의 **모든** 원소에 의해 고정되는 함수 = S₄ 불동점.

조건: 4-순환 Fix 조건 $a_1 = a_2 = a_3 = a_4$에서 모든 변수 계수 동일.

불동점 목록 (2개 자유 매개변수 $a_0, a_1$):

| $a_0$ | $a_1 = a_2 = a_3 = a_4$ | 함수 | 의미 |
|------|----------------------|-----|-----|
| 0 | 0 | $f = 0$ | 상수 0 |
| 1 | 0 | $f = 1$ | 상수 1 |
| 0 | 1 | $f = A \oplus B \oplus C \oplus D$ | **체커보드 (Repo 1 핵심 발견)** |
| 1 | 1 | $f = A \oplus B \oplus C \oplus D \oplus 1$ | 체커보드 보수 |

**결론:** Space(XOR)에서 S₄-불동점은 정확히 4개이며, Repo 1에서 연구의 출발점이 된 체커보드 패턴이 그 중 하나다.

### 2.7 Repo 1과의 연결: 체커보드의 S₄-불동점 특성

> Repo 1 (KMapStructureInvariance)에서 발견된 핵심 결과:  
> "특정 함수들이 변수 치환 하에 K-map 패턴이 불변이다."

이 불변성은 이제 군론으로 정확히 설명된다:

- **O₉의 대표원 $A \oplus B \oplus C \oplus D$**: S₄의 **모든** 원소에 의해 고정 → 완전 S₄-불동점
- **나머지 O₁~O₈ 원소들**: 일부 순열에 의해서만 고정 → 부분 대칭

체커보드가 연구의 출발점이 된 것은 SRT H3(주의 필터) + H4(의미 필터)로 설명되지만,  
그 이면에는 군론적 이유가 있다: **S₄ 불동점 = 가장 대칭적인 함수**.

---

## 3. Space(AND) = M ∩ T₀ ∩ T₁ (단조 클론)의 분석

### 3.1 단조 함수의 구조

4변수 단조 함수의 수: **Dedekind 수 D(4) = 168**

각 단조 함수는 **최소 1(minimal ones)**의 집합 — 즉 **반사슬(antichain)** — 으로 유일하게 특성화된다.

**반사슬:** $\mathcal{A} \subseteq 2^{\{A,B,C,D\}}$의 부분 집합 중, 어떤 두 원소 $S, T \in \mathcal{A}$에 대해 $S \not\subseteq T$인 집합.

**단조 함수 $f_{\mathcal{A}}$:** $f_{\mathcal{A}}(x) = 1$ iff $\exists S \in \mathcal{A}$ such that $S \subseteq \{i : x_i = 1\}$.

### 3.2 Space(AND)의 S₄-불동점 (Fixed Points) — 완전 분류

S₄의 모든 원소에 의해 고정되는 단조 함수 = **완전 대칭 단조 함수 = 임계값 함수(Threshold Functions)**.

**분류 원리:** 임의의 σ ∈ S₄에 대해 f∘σ = f이려면, f는 입력 변수들의 **Hamming 가중치(=1의 개수)**에만 의존해야 한다.

4변수에서 Hamming 가중치별 레이어:
- 가중치 0: {0000} (1개 입력)
- 가중치 1: {A,B,C,D} (4개 입력)
- 가중치 2: {AB, AC, AD, BC, BD, CD} (6개 입력)
- 가중치 3: {ABC, ABD, ACD, BCD} (4개 입력)
- 가중치 4: {ABCD} (1개 입력)

단조 함수가 Hamming 가중치만으로 결정되려면, 1-영역은 "일정 임계값 이상의 가중치" = **위쪽으로 닫힌(upward-closed) 부분집합**이어야 한다.

$\{0,1,2,3,4\}$의 upward-closed 부분집합 (+ empty set):

| 임계값 | 함수 표현 | 설명 |
|------|---------|-----|
| ∅ (없음) | $f = 0$ | 상수 0 |
| $\geq 4$ | $f = A \wedge B \wedge C \wedge D$ | 모두 1일 때만 출력 1 |
| $\geq 3$ | $\text{Maj}_3(A,B,C,D)$ | 3개 이상이 1일 때 출력 1 |
| $\geq 2$ | $\text{Maj}_2(A,B,C,D)$ | 2개 이상이 1일 때 출력 1 |
| $\geq 1$ | $f = A \vee B \vee C \vee D$ | 하나 이상이 1일 때 출력 1 |
| $\geq 0$ | $f = 1$ | 상수 1 |

**결론: Space(AND)의 S₄-불동점은 정확히 6개 (임계값 함수)**

이 6개는 Repo 2 (대칭 Boolean 함수)에서 다루어진 **"대칭이면서 단조인 함수"**의 정확한 목록이다.

$$\text{Fix}(S_4, \text{Space}(AND)) = \{0,\ A \vee B \vee C \vee D,\ \text{Maj}_2,\ \text{Maj}_3,\ A \wedge B \wedge C \wedge D,\ 1\}$$

### 3.3 Burnside 보조정리 적용 — Space(AND)

항등원의 기여는 확실하다: $\text{Fix}(\text{id}, M) = 168$.

나머지 켤레류별 Fix(σ, M)의 계산:

**호환 (AB)에 대한 Fix:**  
$f \circ (AB) = f$인 단조 함수 = A와 B에 대해 대칭인 단조 함수.  
이는 "A와 B를 순서 없는 쌍으로 다루는 4변수 단조 함수"의 수와 같다.

이를 구체적으로 계산하기 위해, A와 B가 대칭인 4변수 단조 함수는 **3-변수 단조 함수의 변형**으로 볼 수 있다. 여기서 세 "변수"는 $A \wedge B$ (둘 다 1), $A \vee B$ (하나 이상 1), 그리고 나머지 $C, D$이다.

**이중 호환 (AB)(CD)에 대한 Fix:**  
$f(A,B,C,D) = f(B,A,D,C)$인 단조 함수.  
{A,B}와 {C,D}가 각각 대칭인 단조 함수. 이는 $A \vee B, A \wedge B, C \vee D, C \wedge D$의 함수로 환원 가능.

**4-순환 (ABCD)에 대한 Fix:**  
네 변수 A→B→C→D→A 순환 대칭이 있는 단조 함수 = 임계값 함수 6개 + 2개 추가 (Fix=8 확인됨).

| 켤레류 | 원소 수 | Fix(σ, M) | 상태 |
|------|--------|---------|-----|
| 항등원 (A)(B)(C)(D) | 1 | 168 | ✅ 확정 |
| 호환 (AB) | 6 | **50** | ✅ 완료 (OC-1) |
| 3-순환 (ABC) | 8 | **15** | ✅ 완료 (OC-1) |
| 4-순환 (ABCD) | 6 | **8** | ✅ 완료 (OC-1) |
| 이중 호환 (AB)(CD) | 3 | **28** | ✅ 완료 (OC-1) |

**Burnside 계산 (OC-1 완료):**
$$|\text{Orbits}(S_4, M)| = \frac{1}{24}(1 \times 168 + 6 \times 50 + 8 \times 15 + 6 \times 8 + 3 \times 28) = \frac{720}{24} = \mathbf{30}$$

**Space(AND)는 S₄ 작용 하에 정확히 30개의 궤도를 가진다.** ✓

> 검증: 직접 궤도 열거(Python 컴퓨터 열거)를 통해 30개 궤도 독립 확인, 크기 합 = 168 ✓

---

## 3.5 Space(NOT) = D (자기쌍대 클론)의 완전 분석 — OC-4

### 3.5.1 자기쌍대 함수의 구조

**자기쌍대(self-dual) 함수:** $f(x) = \neg f(\neg x)$ for all $x \in \{0,1\}^4$.

4변수에서 입력 16개는 8쌍의 **보수 쌍(complementary pairs)** $\{n, \bar{n}\}$ (여기서 $\bar{n} = 15 - n$, 비트별 보수)으로 분류된다:
$$\{0,15\},\ \{1,14\},\ \{2,13\},\ \{3,12\},\ \{4,11\},\ \{5,10\},\ \{6,9\},\ \{7,8\}$$

각 쌍에서 정확히 하나의 원소에 출력 1을 배정해야 하므로, 자기쌍대 함수는 $2^8 = \mathbf{256}$개이다.

**명제 3.5.1:** Space(NOT)는 S₄ 작용 하에 닫혀 있다.

**증명:** $f$가 자기쌍대이고 $\sigma \in S_4$이면,
$$(\sigma \cdot f)(\neg x) = f(\sigma(\neg x)) = f(\neg\sigma(x)) = \neg f(\sigma(x)) = \neg(\sigma \cdot f)(x) \quad \checkmark$$
∎

### 3.5.2 켤레류별 Fix(σ, Space(NOT)) 분석

자기쌍대 함수의 S₄-고정 조건 = **σ-대칭**과 **자기쌍대** 조건의 동시 만족.

**핵심 관찰 — 충돌 메커니즘:** σ의 입력 궤도와 보수 쌍 $\{n, \bar{n}\}$이 **같은 궤도**를 이루면,
$f(n) = f(\bar{n})$ (σ-대칭) 과 $f(n) = \neg f(\bar{n})$ (자기쌍대)가 동시에 요구되어 **해가 없다**.

**켤레류별 분석:**

**항등원:** 모든 16 입력이 독립적. 보수 쌍 8개에서 각각 1비트 자유 → Fix = $2^8 = 256$.

**호환 (AB):** σ 궤도 = {n : x_A≠x_B 인 쌍} + {고정점}. 보수 쌍 $\{5,10\}$과 $\{6,9\}$를 확인하면,  
호환 (AB) 하에서 5(=0101)↔9(=1001), 6(=0110)↔10(=1010)으로 교환되므로  
$\{5,10\}$은 σ-궤도가 아님 (5→9≠10). 충돌 없음. 자유 변수 6개 → Fix = $2^6 = \mathbf{64}$.

**3-순환 (ABC):** σ 궤도 크기 3. 보수 쌍들이 모두 다른 σ-궤도에 걸침. 충돌 없음.  
자유 변수 4개 → Fix = $2^4 = \mathbf{16}$.

**4-순환 (ABCD):** 궤도 $\{5, 10\}$ (크기 2) 확인:  
5=(0101) → σ(5)=(1010)=10 → σ(10)=(0101)=5. 즉 $\{5,10\}$이 σ-궤도.  
그런데 $\{5,10\}$은 보수 쌍이기도 함(15-5=10). → **충돌 → Fix = 0**.

**이중 호환 (AB)(CD):** 궤도 $\{5,10\}$과 $\{6,9\}$ 확인:  
5=(0101) → σ(5)=(1010)=10 (두 쌍 모두 교환). $\{5,10\}$과 $\{6,9\}$ 모두 σ-궤도이며 동시에 보수 쌍 → **충돌 → Fix = 0**.

| 켤레류 | 원소 수 | Fix(σ, Space(NOT)) | 충돌 여부 |
|------|--------|---------|---------|
| 항등원 | 1 | **256** | 없음 |
| 호환 (AB) | 6 | **64** | 없음 |
| 3-순환 (ABC) | 8 | **16** | 없음 |
| 4-순환 (ABCD) | 6 | **0** | ✗ $\{5,10\}$ 충돌 |
| 이중 호환 (AB)(CD) | 3 | **0** | ✗ $\{5,10\}$, $\{6,9\}$ 충돌 |

### 3.5.3 Burnside 적용 (Space(NOT))

$$|\text{Orbits}(S_4, \text{Space(NOT)})| = \frac{1}{24}(1 \times 256 + 6 \times 64 + 8 \times 16 + 6 \times 0 + 3 \times 0)$$
$$= \frac{1}{24}(256 + 384 + 128 + 0 + 0) = \frac{768}{24} = \mathbf{32}$$

**Space(NOT)는 S₄ 작용 하에 정확히 32개의 궤도를 가진다.** ✓

> 검증: Python 컴퓨터 열거(`scripts/s4_orbit_calculator.py`)를 통해 32개 궤도 독립 확인, 크기 합 = 256 ✓

### 3.5.4 S₄-불동점 부재 — 정리

**정리 3.5.2 (Space(NOT)의 S₄-불동점 = 0):**  
Space(NOT)에는 S₄-불동점이 존재하지 않는다.

**증명:**  
S₄-불동점은 Hamming 가중치(HW)에만 의존해야 한다. HW=2 레이어 입력 중 보수 쌍:  
$\{5, 10\}$ (5=0101, 10=1010, HW=2)와 $\{6, 9\}$ (6=0110, 9=1001, HW=2)가 모두 HW=2에 속한다.  
Hamming 가중치에만 의존하면 $f(5) = f(10)$이지만, 자기쌍대 조건은 $f(5) = \neg f(10)$을 요구. 모순. ∎

**함의:** Space(AND)의 6개 불동점(임계값 함수)이 Space(NOT) 내에 대부분 포함되지 않는다.  
(임계값 함수들 중 자기쌍대인 것 = 없음 — 왜냐하면 Maj₂(0000)=0이지만 Maj₂(1111)=1, 자기쌍대 조건 $f(0)=\neg f(15)$ 즉 $0=\neg 1$=참 ✓이지만, Maj₂(0110)=1이고 Maj₂(1001)=1이어서 $f(6)=\neg f(9)$: $1 \neq \neg 1$=거짓 ✗. 따라서 Maj₂는 자기쌍대가 아님.)

### 3.5.5 궤도 크기 분포

| 궤도 크기 | 궤도 수 | 소계 | 안정자 크기 |
|---------|--------|-----|-----------|
| 4 | 16 | 64 | 24/4 = 6 (S₃형 부분군) |
| 12 | 16 | 192 | 24/12 = 2 (호환형 부분군) |
| **합계** | **32** | **256 ✓** | |

---

## 3.6 L ∩ M (아핀이면서 단조인 함수) — OC-5

### 3.6.1 L ∩ M의 원소

**L ∩ M** = 아핀(Space(XOR)) 이면서 단조(Space(AND))인 함수.

아핀 함수 $f = a_0 \oplus \bigoplus_i a_i x_i$ 가 단조이려면, 출력이 어떤 변수도 0에서 1로 바뀔 때 1에서 0으로 감소해선 안 된다. 이를 만족하는 아핀 함수는:

$$L \cap M = \{0,\ 1,\ A,\ B,\ C,\ D\}$$

즉, 상수 0, 상수 1, 그리고 4개의 단일 변수 투영함수 — 총 **6개** (Python 열거로 확인 ✓).

**비-포함 예시:** $A \oplus B$는 아핀이지만 비단조 ($A=1,B=0$ → 1, $A=1,B=1$ → 0).  
$A \oplus 1$ (= ¬A)는 아핀이지만 비단조 ($A=0$ → 1 > $A=1$ → 0).

### 3.6.2 S₄-궤도 (3개)

| 궤도 | 원소 | 크기 | S₄-불동점 | 비고 |
|-----|-----|-----|----------|-----|
| O₁ | $\{0\}$ | 1 | ✓ | 상수 0 |
| O₂ | $\{1\}$ | 1 | ✓ | 상수 1 |
| O₃ | $\{A, B, C, D\}$ | 4 | ✗ | S₄ 타동적 작용 (단일 변수 투영) |

**Burnside 검증:**

| 켤레류 | 원소 수 | Fix(σ, L∩M) | 기여 |
|------|--------|-----------|-----|
| 항등원 | 1 | 6 | 6 |
| 호환 (AB) | 6 | 4 | 24 |
| 3-순환 (ABC) | 8 | 3 | 24 |
| 4-순환 (ABCD) | 6 | 2 | 12 |
| 이중 호환 (AB)(CD) | 3 | 2 | 6 |

$$|\text{Orbits}(S_4, L \cap M)| = \frac{72}{24} = \mathbf{3} \quad \checkmark$$

### 3.6.3 L ∩ M과 Space(AND) S₄-불동점의 관계

$$\text{Fix}(S_4, L \cap M) = \{0, 1\} = \text{Fix}(S_4, \text{Space}(AND)) \cap L$$

Space(AND)의 6개 불동점 중 아핀인 것은 오직 상수 0과 상수 1 뿐.  
→ **단조이면서 아핀이고 S₄-불동점인 함수 = 상수함수 2개만 존재.**

---

## 4. 두 분류의 정제(Refinement) 관계 — Repo 3 ↔ Repo 6 연결

### 4.1 핵심 정리 (FQ-9 공식화)

**정리 4.1 (정제 관계):**  
Repo 3의 S₄ 동치류 분류는 Repo 6의 Space(G) 분류보다 **세밀한(finer)** 분류이다.

$$\text{Space}(G) = \bigsqcup_{i} O_i \quad (\text{S}_4\text{-궤도들의 분리 합집합})$$

즉:
- 같은 S₄-궤도에 속하는 두 함수 → 반드시 같은 Space(G)에 속함
- 같은 Space(G)에 속하는 두 함수 → 반드시 같은 S₄-궤도에 속할 필요 없음

**예시:** Space(XOR)의 O₃ = {A, B, C, D}와 O₅ = {A⊕B, A⊕C, ...}는 모두 Space(XOR) 안에 있지만 서로 다른 S₄-궤도에 속한다.

### 4.2 정제 관계의 시각화

```
전체 65,536개 함수
└── Space(NAND) = Ω (65,536개)
    ├── Space(XOR) = L (32개)
    │   ├── O₁ = {0} (1개)
    │   ├── O₂ = {1} (1개)
    │   ├── O₃ = {A,B,C,D} (4개)
    │   ├── O₄ = {A⊕1,...} (4개)
    │   ├── O₅ = {A⊕B,...} (6개)
    │   ├── O₆ = {A⊕B⊕1,...} (6개)
    │   ├── O₇ = {A⊕B⊕C,...} (4개)
    │   ├── O₈ = {A⊕B⊕C⊕1,...} (4개)
    │   ├── O₉ = {A⊕B⊕C⊕D} (1개) ← Repo 1 출발점
    │   └── O₁₀ = {¬(A⊕B⊕C⊕D)} (1개)
    ├── Space(AND) = M (168개)
    │   ├── 임계값 함수 6개 (S₄-불동점 = 크기 1인 궤도 6개)
    │   └── 나머지 162개 → 30개 궤도 총 (OC-2에 완전 목록)
    └── Space(NOT) = D (256개)
        ├── 크기 4 궤도 16개 (64개 함수)
        └── 크기 12 궤도 16개 (192개 함수)
        ※ S₄-불동점 없음 (정리 3.5.2)

    L ∩ M = {0, 1, A, B, C, D} (6개) → 3궤도 (OC-5)
```

### 4.3 Repo 3 분류와의 대응

Repo 3에서 연구된 "변수 재배열 불변 함수들"은 두 종류로 나뉜다:

**유형 1: S₄-불동점**  
- Space(XOR)의 불동점: {0, 1, A⊕B⊕C⊕D, ¬(A⊕B⊕C⊕D)}
- Space(AND)의 불동점: {0, 1, A∨B∨C∨D, Maj₂, Maj₃, A∧B∧C∧D}
- Space(NOT)의 불동점: **없음** (정리 3.5.2)

**유형 2: S₄ 궤도 내 특정 함수**  
Repo 3에서 "불변 구조"로 등장하는 함수들의 S₄-궤도 대응은 §5 OC-3에 완전히 정리되었다.  
핵심: XOR 체커보드 → Space(XOR) O₉, 임계값 함수 6개 → Space(AND) O01~O06.

---

## 5. 미해결 과제 (Open Computations)

### OC-1: Space(AND)의 Burnside 계산 완성 ✅ 완료

**계산 방법:** Python으로 168개 단조 함수 완전 열거 후 각 켤레류 대표원 적용.

**결과:**

| 켤레류 | 원소 수 | Fix(σ, M) |
|------|--------|---------|
| 항등원 | 1 | 168 |
| 호환 (AB) | 6 | **50** |
| 3-순환 (ABC) | 8 | **15** |
| 4-순환 (ABCD) | 6 | **8** |
| 이중 호환 (AB)(CD) | 3 | **28** |

$$|\text{Orbits}| = \frac{720}{24} = \mathbf{30}$$

> **4-순환 Fix = 8**: 임계값 함수 6개 + α. 순환 대칭 단조 함수가 정확히 8개임을 확인.  
> 추가 2개는: (A∧B)∨(C∧D)류가 아닌, 특수 구조의 단조 함수.

### OC-2: Space(AND)의 S₄-궤도 완전 목록 ✅ 완료

**총 궤도 수: 30개 (컴퓨터 열거 + Burnside 양쪽 검증)**

| 궤도 | 크기 | 대표 함수 | HW 범위 | 비고 |
|-----|------|---------|---------|-----|
| **O01** | 1 | $0$ | — | S₄-불동점, 임계값 함수 |
| **O02** | 1 | $A \wedge B \wedge C \wedge D$ | {4} | S₄-불동점, Threshold-4 |
| **O03** | 1 | $\text{Maj}_3$ (at-least-3) | {3,4} | S₄-불동점, Threshold-3 |
| **O04** | 1 | $\text{Maj}_2$ (at-least-2) | {2,3,4} | S₄-불동점, Threshold-2 |
| **O05** | 1 | $A \vee B \vee C \vee D$ | {1,2,3,4} | S₄-불동점, Threshold-1 |
| **O06** | 1 | $1$ | {0,1,2,3,4} | S₄-불동점, 임계값 함수 |
| **O07** | 3 | $(A \wedge B) \vee (C \wedge D)$ | {2,3,4} | "쌍 AND-OR" (3가지 변수 쌍) |
| **O08** | 3 | $(A \vee B) \wedge (C \vee D)$ | {2,3,4} | "쌍 OR-AND" (3가지 변수 쌍) |
| **O09** | 4 | $B \wedge C \wedge D$ | {3,4} | 3-AND (4가지 변수 선택) |
| **O10** | 4 | $B \wedge C \wedge D \vee A \wedge C \wedge D \vee A \wedge B \wedge D$ | {3,4} | 3개 중 3-AND의 합 |
| **O11** | 4 | $C \wedge D \vee B \wedge D \vee A \wedge D$ | {2,3,4} | "한 변수 고정 OR" |
| **O12** | 4 | $D$ | {1,2,3,4} | 단일 변수 투영 |
| **O13** | 4 | $C \wedge D \vee B \wedge D \vee B \wedge C$ | {2,3,4} | "3쌍 AND" 변형 |
| **O14** | 4 | $C \wedge D \vee B \wedge D \vee A \wedge D \vee A \wedge B \wedge C$ | {2,3,4} | |
| **O15** | 4 | $D \vee A \wedge B \wedge C$ | {1,2,3,4} | |
| **O16** | 4 | $D \vee B \wedge C \vee A \wedge C \vee A \wedge B$ | {1,2,3,4} | |
| **O17** | 4 | $D \vee C \vee B$ | {1,2,3,4} | 3-OR |
| **O18** | 6 | $B \wedge C \wedge D \vee A \wedge C \wedge D$ | {3,4} | |
| **O19** | 6 | $C \wedge D$ | {2,3,4} | 2-AND |
| **O20** | 6 | $C \wedge D \vee A \wedge B \wedge D \vee A \wedge B \wedge C$ | {2,3,4} | |
| **O21** | 6 | $C \wedge D \vee B \wedge D \vee B \wedge C \vee A \wedge D \vee A \wedge C$ | {2,3,4} | |
| **O22** | 6 | $D \vee C$ | {1,2,3,4} | 2-OR |
| **O23** | 6 | $D \vee C \vee A \wedge B$ | {1,2,3,4} | |
| **O24** | 12 | $C \wedge D \vee A \wedge B \wedge D$ | {2,3,4} | |
| **O25** | 12 | $C \wedge D \vee B \wedge D$ | {2,3,4} | $A \wedge (B \vee C)$ 류 |
| **O26** | 12 | $C \wedge D \vee B \wedge D \vee A \wedge B \wedge C$ | {2,3,4} | |
| **O27** | 12 | $C \wedge D \vee B \wedge C \vee A \wedge D$ | {2,3,4} | |
| **O28** | 12 | $C \wedge D \vee B \wedge D \vee B \wedge C \vee A \wedge D$ | {2,3,4} | |
| **O29** | 12 | $D \vee B \wedge C$ | {1,2,3,4} | $(A \wedge B) \vee C$ 류 |
| **O30** | 12 | $D \vee B \wedge C \vee A \wedge C$ | {1,2,3,4} | |

**크기 분포:**

| 궤도 크기 | 궤도 수 | 소계 |
|---------|--------|-----|
| 1 | 6 | 6 |
| 3 | 2 | 6 |
| 4 | 9 | 36 |
| 6 | 6 | 36 |
| 12 | 7 | 84 |
| **합계** | **30** | **168 ✓** |

### OC-3: Repo 3의 "불변 구조"와 S₄-궤도의 대응 확인 ✅ 완료

**결과: Repo 3 핵심 함수 → S₄-궤도 대응표**

| 함수 | 단조 여부 | S₄-불동점 | 궤도 | 궤도 크기 |
|-----|---------|---------|-----|---------|
| **상수 0** | ✓ | ✓ | Space(AND) O01 | 1 |
| **A∧B∧C∧D** | ✓ | ✓ | Space(AND) O02 | 1 |
| **Maj₃** (at-least-3) | ✓ | ✓ | Space(AND) O03 | 1 |
| **Maj₂** (at-least-2) | ✓ | ✓ | Space(AND) O04 | 1 |
| **A∨B∨C∨D** | ✓ | ✓ | Space(AND) O05 | 1 |
| **상수 1** | ✓ | ✓ | Space(AND) O06 | 1 |
| **A∧B** (2-AND) | ✓ | ✗ | Space(AND) O19 | 6 |
| **A∧B∧C** (3-AND) | ✓ | ✗ | Space(AND) O09 | 4 |
| **A∨B** (2-OR) | ✓ | ✗ | Space(AND) O22 | 6 |
| **A∨B∨C** (3-OR) | ✓ | ✗ | Space(AND) O17 | 4 |
| **A** (단일 투영) | ✓ | ✗ | Space(AND) O12 | 4 |
| **(A∧B)∨(C∧D)** | ✓ | ✗ | Space(AND) O07 | 3 |
| **(A∨B)∧(C∨D)** | ✓ | ✗ | Space(AND) O08 | 3 |
| **A∧(B∨C)** | ✓ | ✗ | Space(AND) O25 | 12 |
| **(A∧B)∨C** | ✓ | ✗ | Space(AND) O29 | 12 |
| **XOR A⊕B⊕C⊕D** | ✗ (비단조) | ✓ | Space(XOR) O₉ | 1 |
| **Exactly-1** | ✗ (비단조) | ✓ | Space(AND) 밖 | 1 |
| **Exactly-2** | ✗ (비단조) | ✓ | Space(AND) 밖 | 1 |
| **Exactly-3** | ✗ (비단조) | ✓ | Space(AND) 밖 | 1 |

**핵심 발견:**

1. **Repo 3의 "완전 불변 구조"** = S₄-불동점 = 해당 함수의 카르노맵 패턴이 24가지 변수 배열 모두에서 동일.  
   Space(AND) 내 S₄-불동점은 정확히 6개의 임계값(Threshold) 함수 — Repo 2의 핵심 대상.

2. **체커보드 (A⊕B⊕C⊕D)**: Space(AND) 밖 (비단조), Space(XOR)의 S₄-불동점.  
   Repo 1·3에서 "어떤 배열에서도 체커보드"인 이유가 군론적으로 설명됨. (§2.7 참조)

3. **Exactly-k 함수들**: S₄-불동점이지만 단조 함수가 아니므로 Space(AND) 밖.  
   이들은 Repo 2가 다루는 완전대칭 함수의 부분집합이나, Space(AND)의 S₄-궤도 구조와는 직접 연결되지 않음.

**Theorem 4.1 (정제 관계) 구체적 예시 4개 (OC-3 연동):**

| 예시 | 함수 1 | 궤도 1 | 함수 2 | 궤도 2 | 같은 Space? | 다른 궤도? |
|-----|-------|--------|-------|--------|-----------|---------|
| 1 | A∧B | O19 (크기6) | A∧B∧C | O09 (크기4) | ✓ AND | ✓ |
| 2 | A∨B | O22 (크기6) | A∨B∨C | O17 (크기4) | ✓ AND | ✓ |
| 3 | (A∧B)∨(C∧D) | O07 (크기3) | A∧B | O19 (크기6) | ✓ AND | ✓ |
| 4 | Maj₂ | O04 (크기1) | A∧B | O19 (크기6) | ✓ AND | ✓ |

→ 정제 관계 Theorem 4.1 성립: 동일 Space(AND) 안에서도 S₄-궤도가 다를 수 있음 ✓

---

### OC-4: Space(NOT)의 S₄-궤도 분류 ✅ 완료 (2026-06-23)

**분석 방법:** Burnside 보조정리 (이론적 계산, §3.5) + Python 컴퓨터 열거 독립 검증.

**결과:**

| 켤레류 | 원소 수 | Fix(σ, Space(NOT)) |
|------|--------|---------|
| 항등원 | 1 | 256 |
| 호환 (AB) | 6 | **64** |
| 3-순환 (ABC) | 8 | **16** |
| 4-순환 (ABCD) | 6 | **0** |
| 이중 호환 (AB)(CD) | 3 | **0** |

$$|\text{Orbits}| = \frac{768}{24} = \mathbf{32}$$

> **궤도 크기 분포**: 크기 4 궤도 16개 + 크기 12 궤도 16개 = 총 256개 함수.  
> **S₄-불동점: 0개** — HW=2 레이어의 $\{5,10\}$, $\{6,9\}$ 보수 쌍이 원인. (정리 3.5.2)  
> **4-순환, 이중호환 Fix = 0**: Space(AND)와의 대비 — Space(AND)는 4-순환 Fix=8, 이중호환 Fix=28.

**Space(NOT)과 Space(AND) Fix 비교:**

| 켤레류 | Space(AND) Fix | Space(NOT) Fix | 비교 |
|------|--------------|--------------|-----|
| 항등원 | 168 | 256 | Space(NOT) 더 큼 |
| 호환 | 50 | 64 | Space(NOT) 더 큼 |
| 3-순환 | 15 | 16 | 거의 동일 |
| 4-순환 | 8 | **0** | Space(NOT)만 0 |
| 이중호환 | 28 | **0** | Space(NOT)만 0 |

---

### OC-5: L ∩ M S₄-궤도 확인 ✅ 완료 (2026-06-23)

**분석 방법:** 직접 열거 + Burnside 검증.  
상세 내용: §3.6

**결과:** L ∩ M = $\{0, 1, A, B, C, D\}$ — 6개 함수, **3개 궤도**.

| 궤도 | 크기 | 원소 | S₄-불동점 여부 |
|-----|------|-----|--------------|
| O₁ | 1 | $\{0\}$ | ✓ |
| O₂ | 1 | $\{1\}$ | ✓ |
| O₃ | 4 | $\{A, B, C, D\}$ | ✗ |

$$|\text{Orbits}| = \frac{72}{24} = \mathbf{3}$$

> S₄-불동점 (상수 함수 2개)은 Space(AND) 6개 불동점 중 L에 포함되는 것들.  
> 단조이면서 아핀인 불동점 = 오직 상수 함수 2개.

---

## 6. SRT (H8-H9)와의 연결

### 6.1 S₄ 불동점과 H8 (Concept-as-Lens)

**H8:** 개념이 관찰 렌즈로 작동한다 — 개념을 획득하면 구조로 인식할 수 있는 구성이 확장된다.

**S₄ 불동점의 SRT적 의미:**  
S₄-불동점 함수들 = "어떤 변수 이름을 사용해도 동일하게 인식되는" 함수들. 이 함수들이 연구의 출발점이 된다는 것은 H3(주의 필터)의 예측과 일치한다: "가장 대칭적인 구조"가 주의를 먼저 끈다.

체커보드 (O₉의 원소 = Space(XOR)의 S₄-불동점)는 이 원리의 대표적 실사례이다.

**Space(NOT) 연결:** Space(NOT)에 S₄-불동점이 없다는 사실은, "자기쌍대이면서 완전히 대칭적인" 함수는 존재하지 않음을 의미한다. 이는 H8의 관점에서 "자기쌍대" 개념이 "완전 대칭성" 개념과 긴장 관계에 있음을 암시한다.

### 6.2 궤도 구조와 H9 (Concept Evolution)

**H9:** 연구가 개념을 생성하고, 개념이 새로운 탐구 주기를 가능하게 한다.

Repo 1의 체커보드 발견 → "S₄ 대칭", "Space(XOR)" 개념 형성 → Repo 6에서 전체 10개 궤도 분류 가능 → 새로운 질문 (Space(AND)의 궤도 구조는 어떠한가?) 생성 → 30개 궤도 분류 → 새로운 질문 (Space(NOT)는?) → 32개 궤도, 불동점 부재 발견.

이 개념 발전 경로가 H9의 실사례이다.

---

## 7. 연구 프로그램 연계 요약

| 저장소 | 이 분석과의 연결 |
|------|--------------|
| **Repo 1** (KMapStructureInvariance) | 체커보드 = O₉, Space(XOR)의 S₄-불동점 중 하나 |
| **Repo 2** (SymmetricBooleanFunction) | Maj₂, Maj₃ = Space(AND)의 S₄-불동점 |
| **Repo 3** (VariableRearrangement) | S₄-궤도 분류 = Repo 6 분류의 세밀한 버전 (FQ-9); 완전 대응표는 §5 OC-3 |
| **Repo 4** (SRT) | H3 주의 필터 = S₄-불동점 함수에 먼저 주의 집중; H8-H9의 실사례; Space(NOT) 불동점 부재가 H8에 새 함의 |
| **Repo 6** (이 저장소) | Space(G)의 S₄-궤도 구조 = 새 수학적 기여; Space(AND) 30궤도, Space(NOT) 32궤도 완전 분류 |

---

## 8. 버전 이력

| 버전 | 날짜 | 변경 사항 |
|-----|-----|---------|
| 1.0 | 2026-06-23 | 최초 작성 — Space(XOR)의 완전 분석 (10궤도, Burnside 검증), Space(AND) 불동점 6개, 프레임워크 설정, 미해결 과제 명시 |
| 1.1 | 2026-06-23 | OC-1 완료: Fix(σ,M) 전체 계산 (호환=50, 3-순환=15, 4-순환=8, 이중호환=28), Burnside합=720, 궤도수=30 확정. OC-2 완료: Space(AND)의 S₄-궤도 30개 완전 목록 (크기1×6, 크기3×2, 크기4×9, 크기6×6, 크기12×7). OC-3 완료: Repo 3 핵심 함수들의 S₄-궤도 대응 확인, Theorem 4.1 구체적 예시 4개 제시. |
| 1.2 | 2026-06-23 | OC-4 완료: Space(NOT) 32궤도 분류 (Burnside: 768/24=32, 크기4×16+크기12×16), 켤레류별 Fix 계산 완료 (항등원=256, 호환=64, 3-순환=16, 4-순환=0, 이중호환=0), S₄-불동점 부재 증명 (정리 3.5.2). OC-5 완료: L∩M={0,1,A,B,C,D} 6개 함수의 3궤도 확인 (Burnside: 72/24=3). §3.5, §3.6 신규 절 추가. §4.2 계층도 업데이트. Python 스크립트 `scripts/s4_orbit_calculator.py` 작성 및 전 결과 독립 검증 완료. |

---

*이 문서는 FutureWorks.md §1 (S₄ 군론적 분류, 우선순위 1)의 핵심 수학적 성과 문서이다.*  
*OC-1~OC-5 완료 (2026-06-23). Space(XOR) 10궤도, Space(AND) 30궤도, Space(NOT) 32궤도, L∩M 3궤도 완전 분류 완성.*  
*다음 단계: n=5 확장 기초 스캐폴드 작성, 또는 결과를 SRT 논문(Paper 4)에 H3·H8 근거로 통합.*