The Easy Coefficients Conjecture for rotation-symmetric quadratic Boolean functions

Let II be an index set, let QI,nQ_{I,n} be the associated rotation-symmetric quadratic Boolean function, and set

M(I)=maxiIi.M(I)=\max_{i\in I}i.

Let w1,w2,w_1,w_2,\ldots be the sequence obtained by extending the recursion for the weights of QI,nQ_{I,n} backwards from n=2M(I)+1n=2M(I)+1 to n=1n=1, with wn=wt(QI,n)w_n=\operatorname{wt}(Q_{I,n}) for n2M(I)+1n\geq 2M(I)+1. Let δ1,,δ2M(I)\delta_1,\ldots,\delta_{2^{M(I)}} be the list of irrational roots of the characteristic polynomial of the rules matrix for QI,nQ_{I,n}, with the distinct roots δ1,,δm(Q(I))\delta_1,\ldots,\delta_{m(Q(I))} of the minimal polynomial listed first, followed by duplicates of these roots. Easy Coefficients Conjecture. The resulting sequence satisfies

wn=2n112(δ1n++δ2M(I)n),n=1,2,.w_n=2^{n-1}-\frac{1}{2}\left(\delta_1^n+\cdots+\delta_{2^{M(I)}}^n\right),\qquad n=1,2,\ldots.

The conjecture gives a uniform closed form for the weight recursion of rotation-symmetric quadratic Boolean functions. It is proved for MRS quadratic functions, while the general case for the functions QI,nQ_{I,n} described here is not resolved by the supplied text.

Sources & referencesView supporting material

Primary source

Alexandru Chirvasitu and Thomas W. Cusick, “Quadratic rotation symmetric Boolean functions”, arXiv:2304.12734 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.