Page 140 - 《软件学报》2025年第10期

刘莹 等: 正则图上对称双态自旋系统相关的细密度二分定理 4537

′ ′ ′ ′ ′ ′ ab , −1.
β , 0, 故可归一化为 [a ,1,b ], 满足 a b < {0,±1} 且 a , b . 故不妨设
令 p 是与 a,b,(ab+1),(ab−1) 互素的质数.
2
(1) k = 3. 两个 ( = 3 ) 与通过两个 [a,1,b] 连接, 类似图 4 结构, 可以实现右侧 [a ,1,b ] 函数; 由于 ab , ±1, 则矩
2
( ) ( ) −1
a 2 1 a 2 1
2
2
阵 2 可逆, 可实现左侧 2 即 [b ,−1,a ] 函数. 两个 [0,1] 与一个 (= 3 ) 相连得到右侧 [0,1]; 将其与左
1 b 1 b
( )( )( )
a 1 −1 0 a 1
2 2 2 2 2
侧 [b ,−1,a ] 函数相连得左侧 [−1,a ]; 再将 [−1,a ] 与 (= 3 ) 相连得右侧的 [−1,0,a ]. 通过 2
1 b 0 a 1 b
( )
2
0 a b−a
= 实现左侧 [0,a,ab+1] 函数. 根据引理 7, 得证.
2
2 2
a b−a a b −1
(2) k = 4. 利用 3 个 [0,1] 与 (= 4 ) 相连可得到右侧 [0,1]; 进一步利用 [0,1] 和左侧的 [a,1,b] 连接得到左侧的
2 2 [a,1,b]、
[1,b]; 再利用两个 [1,b] 与一个 (= 4 ) 连接, 可得右侧 [1,0,b ] 函数, 从而得到左侧逆函数 [b ,0,1]. 利用两个
2
2 2 2 [1,0,a ]. 又通过图 类似结构, 可实现
一个 [b ,0,1] 与两个 (= 4 ) 连接, 得到右侧 b [a ,0,1], 进一步得到左侧逆函数 4
3 3 3 3 3 3 [−1,a ]; 再将
3
右侧 [a ,1,b ] 函数, 从而得到左侧对应逆函数 [b ,−1,a ]; 利用 [0,1] 和左侧的 [b ,−1,a ], 可得左侧的
3 6 l ∈ N, 通过
两个 [−1,a ] 与一个 (= 4 ) 连接, 可得右侧 [1,0,a ] 函数. 对于任意

    l  
 1 0  1 0  1 0   1 0 
     
     
    =  
     
0 a 2  0 a 6  0 a 2  0 a 2+8l 
 
可得到左侧的 [1,0,a 2+8l ]. 令 p 是与 a,b,(ab+1),(ab−1) 互素且形如 3+8l 的质数 (由于质数是无限的, 故总能取
到这样的 p), 即存在 l 0 使得 2+8l 0 = p−1, 根据费马小定理, 通过上述构造可获得左侧函数 [1,0,a 2+8l 0 ] = [1,0,1]
2
2
函数. 获得了二元相等函数后无需再注意左右侧. 通过两个 [a,1,b]、一个 [1,0,1] 与两个 (= 4 ) 连接获得 [a ,1,b ],
2 2 2 2 2 2
其逆矩阵为 [b ,−1,a ]; 再利用一个 [a,1,b], 一个 [b ,−1,a ] 和一个 [1,0,1] 与两个 (= 4 ) 连接获得 [ab ,−1,a b].
[a,1,b] 的逆矩阵对应 [b,−1,a], 其与 [0,1] 相连获得 [−1,a]; 利用 (= 4 ) 与 [−1,a] 和 [1,b] 相连获得 [−1,0,ab]; 再利
( )
ab 2 −1
用 两 个 [−1,0,ab] , 一 个 [1,0,1] 与 两 个 ( = 4 ) 连 接 , 形 如 图 4 构 件 , 实 现 [1,0,a b ] . 可 实 现
2 2

2
−1 a b
( )( ) ( ) ( )
2 3
2
2
2 3
1 0 a 1 = 0 ab −a b 函 数 ; 再 利 用 两 个 4 ) 与 0 ab −a b 和

0 a b 1 b a b −a a b −1 ( = [1,0,1] , a b −a a b −1
4 4
4 3
4 4
2 2
4 3
( )
4 3
0 a b −a 相连, 形如图 [0,a b +a b −a b −a b ,a b −1]. 根据引理
3 3
5 5
6 6
2 2
4 4
4 4
4 3
a b −a a b −1 4 构件, 得到 7, 得证.
k −3 k −4
(3) k > 4. 考虑造出左侧 (= 2 ), 从而将 (= k ) 与 或 个 (= 2 ) 相连获得 (= 3 ) 或 ( = 4 ), 回到上述情况.
2 2
k −1 k−1 k−1
若 k 为奇数, 利用一个 (= k ) 与 个 [a,1,b] 相连, 形如图 6 中构件, 实现右侧的 [a 2 ,b 2 ]; 进一步实现左侧
2
k−1 k−1 k−1 k−1
逆函数 [b 2 ,a 2 ]; 再利用一个 (= k ) 与 (k −3)/2 个 [a,1,b] 和一个 [b 2 ,a 2 ] 相连, 实现右端 [b,0,a] 函数, 从而实现左
侧逆函数 [a,0,b]. 通过两个 (= k ) 与 (k −2) 个 [a,1,b] 和一个 [a,0,b] 可以实现右侧的 [a k−1 ,0,b k−1 ]. 对任意 l ∈ N, 通过
[a,0,b],[a k−1 ,0,b k−1 [a kl+1 ,0,b kl+1 a,b,(ab+1),(ab−1) 互素且
由形如 ],...,[a,0,b] 的路径构件实现左侧的 ]. 令 p 是与
形如 kl+2 的质数, 即对某个 l 1 有 p−1 = kl 1 +1, 根据费马小定理, [a kl 1 +1 ,0,b kl 1 +1 ] 实现了左侧 [1,0,1].
k 为偶数, 则与情况 [1,b] 与一
若 (2) 类似, 利用 [0,1] 和左侧的 [a,1,b] 连接得到左侧的 [1,b]; 再利用 (k −2) 个
个 = k 连接, 可得右侧 [1,0,b k−2 ] 函数, 从而得到左侧逆函数 [b k−2 ,0,1]. 利用 (k −2) 个 [a,1,b] 和一个 [b k−2 ,0,1] 与
两个 = k 连接, 得到右侧 b k−2 [a k−2 ,0,1], 进一步得到左侧逆函数 [1,0,a k−2 ]. 又通过图 4 类似结构, 可实现右侧 [a k−1 ,1,b k−1 ]
函数, 从而得到左侧对应逆函数 [b k−1 ,−1,a k−1 ]; 利用 [0,1] 和左侧的 [b k−1 ,−1,a k−1 ], 可得左侧的 [−1,a k−1 ]; 再将 (k −2)
( )(( )( )) l
1 0 1 0 1 0
个 [−1,a k−1 ] 与一个 = k 连接, 可得右侧 [1,0,a (k−1)(k−2) ]. 对任意 l ∈ N, 通过 k−2 (k−1)(k−2) k−2 =
0 a 0 a 0 a
( )
1 0 (k−2)+k(k−2)l
0 a (k−2)+k(k−2)l 实现左侧 [1,,0,a ]. 令 p 是与 a,b,(ab+1),(ab−1) 互素且形如 (k −1)+k(k −2)l 的质数, 即
存在 l 2 使得 (k −1)+k(k −2)l 2 = p−1, 根据费马小定理, 可获得左侧函数 [1,0,a 2+8l 0 (k−2)+k(k−2)l 2 ] = [1,0,1] 函数.
在比#ETH 更强的 rETH 假设下, 本节借助取模运算规避插值, 从而证明了定理 2. 但该方法受到取模运算定