关于「五边形的对称:二面体群 D5 与反对称置换」,《校验码代数与韦尔霍夫算法》给出的定量结论是什么?

结论:第四章从五边形造出 D5,穷举证明模 10 里没有反对称置换,而 D5 有 34040 个。

数据口径:书中录入量、出错率与成本均为示意参数;全部计算由书中程序生成;本书是非个人化经营建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(19 段程序)、原典与作者的假说。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 10, 34040

grouporderanti-symmetric permutations
Z8 (cyclic, even)80
Z9 (cyclic, odd)92025
Z10 (digits mod 10)100
D5 (Verhoeff)1034040
share of all 10! = 3628800 permutations of D5 that work: 0.00938
Z10 search is exhaustive: no single-digit scheme over Z10 with
position maps can catch every single error and every swap
查看完整验算程序
# Chapter 4. p43: counting anti-symmetric maps by exhaustive backtracking.
# A permutation s of a group G is anti-symmetric if x * s(y) != y * s(x)
# whenever x != y. In an abelian group this says that x -> s(x) - x is
# again a permutation (a complete mapping). The search fixes s(0), s(1),
# and so on, and prunes as soon as two values clash. A check scheme
# with one digit from G and position maps s^i catches every single error
# and every neighbour swap iff s is anti-symmetric. Cyclic groups of even
# order have none (Hall and Paige 1955); D5 has many.
import math


def cyclic(n):
    return n, (lambda a, b: (a + b) % n)


def dihedral5():
    def d5(i, j):
        if i < 5 and j < 5:
            return (i + j) % 5
        if i < 5:
            return 5 + (i + j) % 5
        if j < 5:
            return 5 + (i - j) % 5
        return (i - j) % 5
    return 10, d5


def count(n, op):
    s = [None] * n
    used = [False] * n
    found = [0]

    def ok(y, v):
        for x in range(y):
            if op(x, v) == op(y, s[x]):
                return False
        return True

    def place(y):
        if y == n:
            found[0] += 1
            return
        for v in range(n):
            if not used[v] and ok(y, v):
                used[v] = True
                s[y] = v
                place(y + 1)
                used[v] = False
        s[y] = None

    place(0)
    return found[0]


rows = [("Z8 (cyclic, even)", cyclic(8)),
        ("Z9 (cyclic, odd)", cyclic(9)),
        ("Z10 (digits mod 10)", cyclic(10)),
        ("D5 (Verhoeff)", dihedral5())]
print("group                  order  anti-symmetric permutations")
res = {}
for name, (n, op) in rows:
    res[name] = count(n, op)
    print("%-22s %5d  %d" % (name, n, res[name]))
print("share of all 10! = %d permutations of D5 that work: %.5f"
      % (math.factorial(10), res["D5 (Verhoeff)"] / math.factorial(10)))
print("Z10 search is exhaustive: no single-digit scheme over Z10 with")
print("position maps can catch every single error and every swap")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《校验码代数与二面体群韦尔霍夫算法、订单号汇款码书号单字误抄与相邻换位检出率母典》第 4 章「五边形的对称:二面体群 D5 与反对称置换」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-297 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026297,
  author    = {Fan, Yafu},
  title     = {The Algebra of Check Digits and Verhoeff's Dihedral-Group Code: Detection Rates for Single-Digit Slips and Adjacent Transpositions in Order, Remittance and Book Numbers},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论