一个组合猜想及其相关问题的研究

Let w(t) denote the number of 1 in the 2-ary expansion of a positive integer t. In 2009, Ziran Tu and Yingpu Deng proposed the following combinatorial conjecture: Let X={(a,b): a and b are nonnegative integers smaller than 2^k, a+b is congruence to t modulo 2^k-1, and w(a)+w(b)<k}. Then |X| is smaller or equal to k-1 powers of 2. Under the assumption that the conjecture is true, they obtained two classes of Boolean functions which are both algebraic immunity optimal and have high nonlinearity. Since Boolean functions play an important role in cryptography, this conjecture was generalized to more general form soon and more classes of Boolean functions were constructed under the assumption that the general form is true. There are only a few cases of the conjecture which have been proved so far. This project will investigate the original conjecture by using probability and combinatorial methods.

我们记正整数t的权w(t)为它的2进展开式中1的个数。设正整数t,k满足t小于2的k次幂。涂自然和邓映蒲在2009年提出了下面这个组合猜想：令X={(a,b): a,b是非负整数且小于2的k次幂，a+b与t模2^k-1同余，且w(a)+w(b)<k}，则X包含的元素的个数小于2的k-1次幂。并且在这个猜想成立的前提下构造了两类具有最优代数免疫度的布尔函数，并且具有高度的非线性性。由于布尔函数在密码学中有着非常重要的地位。这个猜想很快引起了人们的注意，并被推广到了更一般的形式，并且类似的在推广的猜想成立的前提下也构造了几类具有很好性质的布尔函数。这个猜想目前得到的结果还不多。本项目将利用概率和组合的方法研究这个猜想。

布尔函数在密码学中有着重要的应用。通常人们希望得到的布尔函数能有一些比较好的密码性质，如高度非线性性，高代数次数，高代数免疫度等等。一般的，很难找到布尔函数满足很多这样好的密码性质。涂自然和邓映蒲2009年在提出了下面组合猜想。设正整数t,k满足t小于2的k次幂，令X={(a,b):a,b是非负整数且小于2的k次幂，a+b与t模2的k次幂同余，且w(a)+w(b)<k}, 其中w(x)是x的2进展开中出现的1的个数。那么集合X包含的元素不大于2的k-1次幂。在这个组合猜想成立的情况下他们构造了两类具有最优代数免疫度的不二函数，并且具有高度的非线性性。这个猜想以及相关的构造良好布尔函数的方法很快引起了人们的注意，并被推广到了许多其他形式。某些推广的猜想得到了证明，但是原本的这个组合猜想的结果并不多，人们证明了当t取某些值的时候，X的大小的上界2的k-1次幂是可以达到的。申请项目之前申请人的结果是用组合方法证明了对于某类t，这个猜想是成立的。在项目的进一步研究中，由于该组合方法难以进一步推广，该猜想的研究只得到了一些零散的结论，没有得到更进一步的系统性结果。