Math Pro 數學補給站

複製內容到剪貼板

代碼:

# 要執行此程式碼，您需要先安裝 galois 函式庫。

# 您可以使用 pip 來安裝：

# pip install galois



import galois



def construct_singer_set(q, m):

    """

    根據 Coulbourn 和 Dinitz 的手冊中描述的 Singer 差集構造法，

    使用「跡函數」來產生一個差集。



    參數:

    q (int): 基體的階數，必須是質數的冪次方。

    m (int): 擴張體的次數。

    

    返回:

    list: 一個包含差集元素的已排序列表。

    """

    print(f"--- 正在為 q={q}, m={m} 構造 Singer 差集 ---")

    

    try:

        # 步驟 1: 建立有限體 GF(q) 和擴張體 GF(q^m)

        # 這是所有計算的基礎環境。

        GF_q = galois.GF(q)

        GF_qm = galois.GF(q**m)

        #自行加上repr="poly"以多項式呈現，irreducible_poly="x^6+x+1"指定哪個本原多項式計算

        #GF_qm = galois.GF(q**m,repr="poly",irreducible_poly="x^6+x+1")

        print(f"成功建立有限體 GF({q}) 和擴張體 GF({q}^{m})。")

    except TypeError as e:

        print(f"錯誤：無法建立有限體。請確保 q={q} 是一個質數的冪次方。")

        print(f"原始錯誤訊息: {e}")

        return None



    # 步驟 2: 找到擴張體 GF(q^m) 的一個生成元 (primitive element) alpha

    # 這對應文件中提到的 "let α be a generator"。

    alpha = GF_qm.primitive_element

    print(f"找到一個生成元 alpha = {alpha}")



    # 步驟 3: 實現跡函數 (Trace function)

    # Tr(x) = x + x^q + ... + x^(q^(m-1))

    def trace(x):

        """計算元素 x 從 GF(q^m) 到 GF(q) 的跡。"""

        tr = GF_qm.Zeros(1) # 初始化為 0

        for i in range(m):

            tr += x**(q**i)

        return tr



    # 步驟 4: 計算參數 v

    v = (q**m - 1) // (q - 1)

    k = (q**(m-1) - 1) // (q - 1)

    lambda_val = (q**(m-2) - 1) // (q - 1) if m > 1 else 1

    print(f"差集參數: (v, k, λ) = ({v}, {k}, {lambda_val})")



    # 步驟 5: 遍歷 alpha 的次方，並用跡函數篩選

    # 根據定義，差集是 {i in Z_v | Tr(alpha^i) = 0}

    print(f"正在遍歷 i 從 0 到 {v-1}，並檢查 Tr(alpha^i) 是否為 0...")

    difference_set = []

    for i in range(v):

        element = alpha**i

        trace_value = trace(element)

        

        # 檢查跡函數的結果是否為 GF(q) 中的零元素

        if trace_value == 0:

            difference_set.append(i)

            # print(f"  Tr(alpha^{i}) = Tr({element}) = {trace_value} -> 找到一個元素: {i}")



    print("構造完成！")

    return sorted(difference_set)



# --- 主執行區塊 ---

if __name__ == '__main__':

    # 範例：對應您文件中提到的 q=4, m=3 的情況

    # 這將產生一個 (21, 5, 1) 差集

    q_val = 4

    m_val = 3

    

    ds = construct_singer_set(q_val, m_val)

    

    if ds:

        print(f"\n對於 q={q_val}, m={m_val}，構造出的 Singer 差集為:")

        print(f"D = {ds}")

        # 預期結果之一: [0, 1, 4, 14, 16] 或其他等價集合

        # 注意：由於生成元 alpha 的選擇不是唯一的，

        # 最終產生的差集可能會是已知答案的一個等價形式（例如乘以某個常數後取模）。

        # 但它必定是一個有效的 (21, 5, 1) 差集。



    print("\n" + "="*50 + "\n")



    # 另一個經典範例: q=2, m=3 (Fano 平面)

    # 這將產生一個 (7, 3, 1) 差集

    q_val_fano = 2

    m_val_fano = 3

    

    ds_fano = construct_singer_set(q_val_fano, m_val_fano)



    if ds_fano:

        print(f"\n對於 q={q_val_fano}, m={m_val_fano}，構造出的 Singer 差集為:")

        print(f"D = {ds_fano}")

        # 預期結果之一: [0, 1, 3]

複製內容到剪貼板

代碼:

--- 正在為 q=4, m=3 構造 Singer 差集 ---

成功建立有限體 GF(4) 和擴張體 GF(4^3)。

找到一個生成元 alpha = 2

差集參數: (v, k, λ) = (21, 5, 1)

正在遍歷 i 從 0 到 20，並檢查 Tr(alpha^i) 是否為 0...

構造完成！



對於 q=4, m=3，構造出的 Singer 差集為:

D = [7, 9, 14, 15, 18]



==================================================



--- 正在為 q=2, m=3 構造 Singer 差集 ---

成功建立有限體 GF(2) 和擴張體 GF(2^3)。

找到一個生成元 alpha = 2

差集參數: (v, k, λ) = (7, 3, 1)

正在遍歷 i 從 0 到 6，並檢查 Tr(alpha^i) 是否為 0...

構造完成！



對於 q=2, m=3，構造出的 Singer 差集為:

D = [1, 2, 4]

\(GF(2^3)\)的Primitive Irreducible polynomial為\(x^3+x+1\)	\(GF(2^3)\)的Primitive Irreducible polynomial為\(x^3+x^2+1\)
多項式先同餘\(x^3+x+1\)，係數再同餘\(2\) \(i=0,Tr(\alpha^0)=x^0+x^0+x^0=1+1+1=3=1\) \(\bbox[border:1px solid black]{i=1},Tr(\alpha^1)=x+x^2+x^4=x+x^2+(-x^2-x)=0\) \(\bbox[border:1px solid black]{i=2},Tr(\alpha^2)=x^2+x^4+x^8=x^2+(-x^2-x)+(-3x-2)=-4x-2=0\) \(i=3,Tr(\alpha^3)=x^3+x^6+x^{12}=(-x-1)+(x^2+2x+1)+(5x^2-x-3)=6x^2-3=1\) \(\bbox[border:1px solid black]{i=4},Tr(\alpha^4)=x^4+x^8+x^{16}=(-x^2-x)+(-3x-2)+(9x^2+12x+4)\) 　　　　　\(=8x^2+8x+2=0\) \(i=5,Tr(\alpha^5)=x^5+x^{10}+x^{20}=(-x^2+x+1)+(-2x^2+3x+3)+(-7x^2+26x+21)\) 　　　　　\(=-10x^2+30x+25=1\) \(i=6,Tr(\alpha^6)=x^6+x^{12}+x^{24}=(x^2+2x+1)+(5x^2-x-3)+(-54x^2-9x+19)\) 　　　　　\(=-48x^2-8x+17=1\) 收集\(Tr(\alpha^i)=0\)的\(i\)形成Difference Set為\(\{\;1,2,4 \}\;\)	多項式先同餘\(x^3+x^2+1\)，係數再同餘\(2\) \(i=0,Tr(\alpha^0)=1+1+1=3=1\) \(i=1,Tr(\alpha^1)=x+x^2+x^4=x+x^2+(x^2-x+1)=2x^2+1=1\) \(i=2,Tr(\alpha^2)=x^2+x^4+x^8=x^2+(x^2-x+1)+(6x^2-3x+4)=8x^2-4x+5=1\) \(\bbox[border:1px solid black]{i=3},Tr(\alpha^3)=x^3+x^6+x^{12}=(-x^2-1)+(3x^2-x+2)+(28x^2-13x+19)\) 　　　　　\(=30x^2-14x+20=0\) \(i=4,Tr(\alpha^4)=x^4+x^8+x^{16}=(x^2-x+1)+(6x^2-3x+4)+(129x^2-60x+88)\) 　　　　　\(=136x^2-64x+93=1\) \(\bbox[border:1px solid black]{i=5},Tr(\alpha^5)=x^5+x^{10}+x^{20}=(-2x^2+x-1)+(13x^2-6x+9)+(595x^2-277x+406)\) 　　　　　\(=606x^2-282x+414=0\) \(\bbox[border:1px solid black]{i=6},Tr(\alpha^6)=x^6+x^{12}+x^{24}=(3x^2-x+2)+(28x^2-13x+19)+(2745x^2-1278x+1873)\) 　　　　　\(=2776x^2-1292x+1894=0\) 收集\(Tr(\alpha^i)=0\)的\(i\)形成Difference Set為\(\{\;3,5,6 \}\;\)
\(D=\{\;1,2,4\}\;\)和\(\{\;0,1,3\}\;\)同構 \(D+1=\{\;2,3,5\}\;\) \(D+2=\{\;3,4,6\}\;\) \(D+3=\{\;4,5,0\}\;\) \(D+4=\{\;5,6,1\}\;\) \(D+5=\{\;6,0,2\}\;\) \(D+6=\{\;0,1,3\}\;\)	\(D=\{\;3,5,6\}\;\)和\(\{\;0,1,5\}\;\)同構 \(D+1=\{\;4,6,0\}\;\) \(D+2=\{\;5,0,1\}\;\) \(D+3=\{\;6,1,2\}\;\) \(D+4=\{\;0,2,3\}\;\) \(D+5=\{\;1,3,4\}\;\) \(D+6=\{\;2,4,5\}\;\)