STEP 1662 · 2026-09-02 · rei-aios · 掛谷 arc A-2

F_q^n 掛谷集合の greedy 最小化
4 次元有限体での貪欲 line-selection の実測

F_q^n の掛谷集合 K = 「全ての方向に少なくとも 1 本の直線を含む部分集合」を、方向をランダム順に走査し各方向について「既存 covered set に追加点最小」の平行線を選ぶ貪欲 heuristic で 8 実験。主 target = F_3^4 (81 点、 40 方向、 27 lines/direction)。 sanity として F_3^2 (既知 min = 7) と F_5^2 (既知 min ≈ 15-17) も含めた。

結果 (min = 30 trial の中の最小 greedy)

体	全点数	方向数	Dvir LB	Origin 星	greedy min	random min	min/Dvir	min/全
F₃²	9	4	6	9	7	7	1.17	0.778
F₅²	25	6	15	25	17	17	1.13	0.680
F₃³	27	13	10	27	15	16	1.50	0.556
F₃⁴	81	40	15	81	31	57	2.07	0.383
F₅³	125	31	35	125	55	84	1.57	0.440
F₅⁴	625	156	70	625	215	435	3.07	0.344
F₇³	343	57	84	343	151	231	1.80	0.440
F₃⁵	243	121	21	243	70	179	3.33	0.288

min |K| vs 全空間 (log-log 軸)

要点 3 件

F₃² の greedy min = 7 は既知の有限体掛谷 min |K| = 7 (Ellenberg-Erdélyi) と一致 = sanity check pass。 greedy は 2 次元では最適に触れている。
F₃⁴ (主 target) で greedy min = 31 点、全空間 81 の 38%、 Dvir LB = 15 の 2.07 倍。 random min = 57 (=70%) を greedy がほぼ半減 = 貪欲が effective。
Dvir LB は loose — n≥3 で greedy min / Dvir LB = 1.5-3.3 倍の gap。実際の min はいずれかに挟まれているが、 SAT/ILP 実装で greedy をさらに下回れる余地は大きい。特に F₃⁴ で 20-25 点まで下がる可能性。

アルゴリズム

1. F_q^n の 全 q^n 点 を 列挙
2. PG(n-1, q) の 方向 を 列挙 = (q^n - 1)/(q - 1) 個
   (代表 = 最初の 非零 成分 が 1 の ベクトル)
3. 各 方向 d について、 全 q^(n-1) 個 の 平行 直線 を 列挙
4. GREEDY:
   ・ 方向 を ランダム順 に shuffle
   ・ 各 方向 について、 その 方向 の 平行線 の 中から
     「既に covered に 入っている点数 が 最大」 = 「追加点 が 最小」 の line を 選ぶ
   ・ 30 trial の 最小 を report
5. RANDOM baseline: 各 方向 について ランダム line を 選ぶ

掛谷 arc 内の位置

#	実験	状態	結果 hook
A-3	enwik8 baseline (STEP 1656)	✓	xz -9e bpc 1.99 最良
A-1	NCD clustering (STEP 1661)	✓	solid xz -9e を上回れず (反証)
A-2	F_q^n 掛谷 greedy (本 STEP 1662)	✓	F_3^4 min = 31 (38% of space)
—	next: SAT/ILP に置き換え	候補	greedy 31 → 20 台期待

Honest scope

本実装は prime q のみ (2, 3, 5, 7)。 q=4 = GF(2^2) や q=8 は多項式 mod 2 arithmetic が必要で未実装 (scope 外)。
greedy min は true minimum ではない — heuristic の下界、 SAT/ILP で下回れる余地。
Dvir LB は多項式法の下界、実際の min はこれと greedy min の間。 gap の大きさ (n≥3 で 1.5-3.3 倍) が SAT 探索の意義を示す。
F_3^2 で既知 min = 7 と一致は sanity、 F_3^4 等で「greedy が true min」を主張しない (未証明)。
5 次元 F_3^5 も参考実装 (min = 70)、前 turn 議論の通り 4 次元完了後の次元拡張として code 流用で実行 (実装コスト ~ゼロ)。

成果物

data/kakeya/results-step1662.json — 8 case × greedy/random trial 詳細
scripts/kakeya-finite-field/run-kakeya.py — 実装
本 site page + dist-renderer/tools/ mirror force-track

F_q^n 掛谷集合 の greedy 最小化4 次元 有限体 での 貪欲 line-selection の 実測

結果 (min = 30 trial の 中の 最小 greedy)