4t?1 元旋轉對稱2-彈性函數的構造

杜蛟，劉春紅，龐善起

（1.河南師范大學數學與信息科學學院，河南 新鄉 453007；2.河南師范大學大數據統計與優化控制河南省工程實驗室，河南 新鄉 453007；3.河南師范大學計算機與信息工程學院，河南 新鄉 453007）

1 引言

文獻[2-3]首先研究了具有相關免疫性和高非線性度的旋轉對稱布爾函數；文獻[9-11]研究了平衡的旋轉對稱布爾函數以及相關免疫旋轉對稱布爾函數的構造與計數問題；文獻[12]研究了相關免疫階的判別問題；文獻[13-17]研究了旋轉對稱1-彈性函數的若干具體構造方法；文獻[18]給出了一個旋轉對稱彈性函數的二級構造方法，但是該方法依賴于已有的低階彈性旋轉對稱函數，構造的函數的變元個數局限性較大；文獻[19-20]進一步將旋轉對稱彈性函數的構造問題從特征為 2 的有限域上推廣到特征為奇素數的有限域上。基于以上結果，本文基于軌道交換方法給出了一類具有4t?1 個變元的旋轉對稱2-彈性函數的構造方法。

2 預備知識

n元布爾函數f0(x)=x1+x2+…+xn不僅是一個n?1階的彈性函數，還是一個旋轉對稱布爾函數，記f1(x)=1+x1+x2+…+xn=1+f0(x)，定義

注意到，f1(x)為旋轉對稱函數的條件是當且僅當集合T是某個旋轉對稱函數的支撐集[21]，即為若干個旋轉對稱軌道的并集。向量x=(x1,x2,…,xn)∈的漢明重量為其分量中1 的個數，記為 wt(x)。

定義 1[15]設f(x)∈Bn，記1f={x∈|f(x)=1}，若有|1f|=2n?1，則稱f(x)是一個平衡函數，1f是布爾函數f(x)的支撐集或支撐矩陣，集合1f中的向量稱為f(x)的支撐向量，1+f(x)的支撐集或支撐矩陣簡記為0f。

定義2[22-23]對于有限域F2上的w×n維矩陣A，如果線性空間中的每一個向量都在矩陣A的任意d列中出現相同的次數，則稱A是一個正交表 OA(w,n,2,d)。

定義3[23]如果V0和V1都是 OA(2n?1,n,2,d)，滿足V0∩V1=?，且V0∪V1=，則稱{V0,V1}為一個強度為d的正交表大集，記為 LOA(2n?1,n,2,d)。

文獻[23]給出了相關免疫函數和彈性函數與正交表和正交表大集間的關系，如果一個布爾函數f(x)的支撐矩陣1f是一個正交表OA(w,n,2,d)，則稱f(x)是一個d階相關免疫函數。如果f(x)既是平衡的，又是一個d階相關免疫函數，則f(x)是一個d-彈性函數，從定義3 可知，d-彈性函數的構造等價于強度為d的正交表大集LOA(2n?1,n,2,d)的構造，本文中的正交均指組合正交性。

下面，考慮循環群Cn=≤l≤n?1}在上的作用，變換定義為

3 旋轉對稱軌道的性質

為了研究旋轉對稱 2-彈性函數的構造，下面將在文獻[15]的基礎上進一步研究旋轉對稱軌道的性質。假設變元個數n=4t?1，其中t為正整數。

引理1[8]n元旋轉對稱長軌道的總數為

其中，μ(g)為墨比烏斯函數。

引理2[15]設f(x)為n元旋轉對稱布爾函數，1f=(c1,c2,…,cn)為f(x)的支撐矩陣，其中ci為1f的第i個列向量，那么存在一個置換矩陣P滿足ci+1=Pci,1≤i≤n?1。

引理3[15]設f(x)為n元旋轉對稱布爾函數，1f=(c1,c2,…,cn)為f(x)的支撐矩陣，ci為1f的第i個列向量，那么f(x)是2 階相關免疫函數的條件是當且僅當(c1,ck)是一個，其中，。

注：引理3 說明要判斷1f是否是強度為2 的正交表，只需判斷第1 列與第2～k列分別正交即可，這個結果大大簡化了1f是否是強度為2 的正交表的判斷過程。

定理1設ROx是n維向量在循環群的作用下生成的一個旋轉對稱長軌道，則矩陣ROx的任意2 列中，數對01 和10 出現的次數一定相等。

證明由引理2 可知，適當排列ROx的行向量，則ROx可以表示為

其中，di和dj分別是ROx的第i列和第j列，1≤i＜j≤n。下面，考慮di和dj這2 列中數對01和10 出現的次數。根據引理2，dj可以看作由di循環移位得到的，它們的分量中0 的個數和1 的個數分別相等，即如果列向量di的漢明重量wt(di)=w，則wt(dj)=w，其中，1≤i＜j≤n。不妨設由di和dj這2 個列向量構成的n×2矩陣為

該矩陣行向量構成的n個數對中00、01、10、11 出現的次數分別為N00、N01、N10、N11，則有式(2)所示的方程組成立。

由式(2)中第一個和第三個方程可知N01=N10，這就證明了矩陣ROx的任意2 列中，數對01 和10出現的次數一定相等。

注：①由式(2)可知，ROx的任意2 列中，數對11 和00 出現的次數之差為N11?N00=2w?n；②定理1 說明，一個軌道矩陣的任意2 列構成的子矩陣的行向量中，數對00、01、10 和11 出現的次數實際上是由00、01 和11 這3 種數對確定的；③如果ROx是一個短軌道，且1 ＜|ROx|＜n，定理1的結論不一定成立。根據上面的性質，為簡化問題，本文給出如下定義。

定義4設n維向量在循環群的作用下生成的旋轉對稱的長軌道為

在ROx的第1 列和第列中，數對00、01、11 出現的次數分別為bk?1,1、bk?1,2、bk?1,3，則稱如下的矩陣

為旋轉對稱軌道ROx的數對分布矩陣。

特別地，若0r和1r分別表示r個連續的0和r個連續的1 構成的行向量，則軌道{0n}和{1n}的數對分布矩陣為矩陣，即

對于n維向量x=(x1,x2,…,xn)，若，則容易證明在循環群Cn的作用下生成的旋轉對稱軌道的數對分布矩陣為

文獻[15]給出了旋轉對稱彈性函數的支撐矩陣的性質，并給出了旋轉對稱2-彈性函數的等價刻畫，但是不能給出具體的構造方法，為了構造出具體的旋轉對稱2-彈性函數，本文首先給出定理2。

定理2若t為正整數，當n=4t?1時，則對任意的漢明重量為2t的向量，生成的軌道矩陣的數對分布矩陣為

證明當n=4t?1時，對任意的漢明重量為的向量x=(x1,x2,…,xn)，由于2t與4t?1互素，故該向量生成的旋轉對稱軌道一定是長軌道。根據軌道矩陣對應的數對分布矩陣的定義，在定理1 中，向量x=(x1,x2,…,xn)的漢明重量為w=2t，由式(2)可得，N11?N00=2w?n=1，這說明向量x=(x1,x2,…,xn)所在的軌道矩陣中由任意2 個列向量di和dj構成的n×2維矩陣的行向量構成的數對11 的個數N11總比數對00 的個數N00多1。令i=1，j跑遍集合{2,3,…,2t}，可得，即向量。證畢。

4 4t?1 元旋轉對稱2-彈性函數的一個新的等價刻畫

定理3對于式(1)所定義的函數f(x)，則f(x)是旋轉對稱2-彈性函數的充分必要條件是集合T滿足如下2 個條件。

1)T可以分解為集合S0和S1，使T=S0∪S1，其中

且|S0|=|S1|，其中，m和m'為非負整數，l1,l2,…,lm和s1,s2,…,sm'在集合{0,1,…,2t?1}中取值。

2)S0中不同的旋轉對稱軌道對應的數對分布矩陣之和與S1中不同的旋轉對稱軌道對應的數對分布矩陣之和相等。

證明必要性。如果f(x)是旋轉對稱2-彈性函數，這意味著f(x)既是2-彈性函數，也是旋轉對稱函數。由于f(x)是2-彈性函數，根據彈性函數與正交表大集間的等價關系可知，{1f,0f}是上的一個強度為 2 的正交表大集，故1f和0f都是 OA(2n?1,n,2,2)。由于f(x)是旋轉對稱函數，1f和0f一定都是若干個旋轉對稱軌道的并集。另一方面，對1f中的旋轉對稱軌道進行分類，將向量的漢明重量為偶數的所有旋轉對稱軌道記為S0，顯然S0可表示為一些旋轉對稱軌道的并集，即

對0f中的旋轉對稱軌道進行分類，將其中向量的漢明重量為奇數的旋轉對稱軌道記為S1，顯然S1也可表示為一些旋轉對稱軌道的并集，即

其中，m和m'為非負整數，l1,l2,…,lm和s1,s2,…,sm'在集合{0,1,…,2t?1}中取值，n=4t?1，故f(x)的支撐集可以表示為，由f(x)是平衡的，可知|S0|=|S1|，故條件1)成立。而由是一個OA(2n?1,n,2,n?1)可知，也是一個OA(2n?1,n,2,2)，這就意味著在的任意2 列中，數對00、01、10、11 出現的次數均為 2n?3，由于1f和都是OA(2n?1,n,2,2)，因而在1f的任意2 列中，以及在的任意2 列中，數對00、01、10、11 出現的次數均為 2n?3，注意到

這說明S0中不同的旋轉對稱軌道對應的數對分布矩陣之和與S1中不同的旋轉對稱軌道對應的數對分布矩陣之和相等，即條件2)成立。必要性證畢。

充分性。由于f0(x)=x1+x2+…+xn是一個n元旋轉對稱彈性函數，故當條件1)成立時，注意到T=S0∪S1，且S0和S1均為一些旋轉對稱軌道的并集，因而T可以看作一個旋轉對稱函數的支撐集，從而條件1)中定義的函數f(x)是一個旋轉對稱函數；再由f0(x)是彈性函數以及T=S0∪S1和|S0|=|S1|可知，f(x)是平衡函數；由正交表與彈性函數的關系，只需證明1f是強度為2 的正交表即可。

根據條件2)，由S0中不同的旋轉對稱軌道對應的數對分布矩陣之和與S1中不同的旋轉對稱軌道對應的數對分布矩陣之和相等可知，式(1)所定義的函數f(x)的支撐矩陣1f的 1 列分別與第列正交，再根據旋轉對稱函數的支撐矩陣的性質以及引理3 可知，f(x)的支撐矩陣1f是一個OA(2n?1,n,2,2)。充分性證畢。

由定理3 可知，旋轉對稱2-彈性函數的構造等價于尋找滿足定理3 條件的集合T，其中條件1) 是為了保證所構造的函數是平衡的旋轉對稱函數，條件2) 是為了保證所構造的函數是2-彈性的，利用定理1 和定理2 得到的結果，借助于定理3，可以構造旋轉對稱2-彈性函數的無窮類，結合下面的例子，來說明本文方法的有效性。

5 一個構造性的例子

以7 元旋轉對稱2-彈性函數的構造為例，來說明本文的定理在一類4t? 1元旋轉對稱彈性函數的構造中的應用。由引理1 以及文獻[13]中的計算可知，若n=4t? 1為素數，則循環群Cn在上的作用形成的軌道中，只有2 個短軌道{0n}和{1n}，其他的均為長軌道。特別地，對于循環群作用在上，形成和這2 個短軌道，以及18 個長軌道。為了方便，本文將旋轉對稱軌道及其對應的數對分布矩陣分別表示為

行向量的漢明重量為3 和4 的軌道有如下10 個，其中，對應的數對分布矩陣。

由定理3 可知，要構造不同的7 元旋轉對稱2-彈性函數，關鍵在于確定不同的S0和S1。若S0和S1中分別有2 個軌道，且其中之一是短軌道時，可以有如下的7 種方案。

當S0和S1按照上面的 7 種方案確定，取T=S0∪S1時，有|S0|=|S1|，對于式(1)定義的f(x)，根據定理3 可知，f(x)均為旋轉對稱2 階彈性函數。其中方案 1 確定的T=S0∪S1=，可以根據T中的向量計算所構造函數的代數正規型。當變元個數n=4t?1較大時，如何根據所構造函數的支撐矩陣得到其代數正規型，計算其非線性度是一個有待進一步解決的問題。

6 結束語

旋轉對稱函數由于其特殊的結構及其廣泛的應用受到越來越廣泛的研究，關于旋轉對稱1-彈性函數的構造與計數已經有較多的結果，本文基于旋轉對稱軌道的數對分布矩陣的性質，給出了一個旋轉對稱2-彈性函數的直接構造方法，該方法能構造出無窮多個旋轉對稱2-彈性函數，但是由于所給出的函數都是以支撐集的形式給出的，因而不能給出所構造函數的具體的代數正規型，或者說，需要煩瑣的計算轉換才能給出代數正規型，因而也就不能直接地給出其代數次數。其次，已有的一些文獻對所構造的RSBF 是基于擇多函數得到的，因而對非線性度的估計計算有較多的數學工具可用，而本文構造的函數是通過修改線性函數f0(x)=x1+x2+…+xn的支撐集而得到的，對其非線性度的計算也有較大的難度，這也是本文的一個不足。尋找有效地計算本文中所構造的旋轉對稱2-彈性函數的代數表達式與非線性度將是下一步要解決的問題。