Symbolic dynamics and rotation symmetric Boolean functions (Q2088956): Difference between revisions

A Boolean function \(f_n\colon \{0,1\}^n \to \{0,1\}\) is \textit{rotation symmetric} if it is invariant under cyclic rotation of the input. These functions can always be written as an XOR of the functions \[ f^{a_1,\dots,a_{d-1}}_n(x_0,\dots,x_{n-1}) = \bigoplus_{i=0}^{n-1} x_i x_{i+a_1 \bmod n} \cdots x_{i+a_{d-1} \bmod n}. \] Each vector \(a_1,\dots,a_{d-1}\) defines an infinite sequence of functions, one for each value of \(n\). It is thus natural to study the beahior of functions of the form \[ f^{\mathcal{C}}_n = \bigoplus_{\vec{a} \in \mathcal{C}} f^{\vec{a}}_n \] as a function of \(n\). \textit{T. W. Cusick} [IEEE Trans. Inf. Theory 64, No. 4, Part 2, 2962--2968 (2018; Zbl 1392.94967)] considered the \textit{weights} of the functions \(f^{\mathcal{C}}_n\) (the number of \(1\)-inputs), showing that they satisfy a linear recurrence. In this paper, the authors rederive this result by relating rotation symmetric Boolean functions to \textit{shifts}, which are subsets of \(k^\mathbb{Z}\) closed under cyclic shifts, for some field \(k\). Using an elegant reduction, they show that the co-weight of \(f^{\mathcal{C}}_n\) coincides with the number of \(n\)-periodic sequences in a shift of finite type over \(\mathrm{GF}(2)^2\). These numbers are classically known to satisfy a linear recurrence. The authors then extend their work to an analog of rotation symmetric functions in which the input is identified with an element of \(\mathrm{GF}(2^n)\), and the output is an XOR of traces of powers of the input. In this case, the reduction is to the number of points on an algebraic curve. Using their techniques, the authors determine explicitly the linear recurrence for the sequence \(f^t_n\), that is, for the functions \[ f^t_n(x_0,\ldots,x_{n-1}) = \bigoplus_{i=0}^{n-1} x_i x_{i+t}. \] The coefficients of the linear recurrence have a particularly nice form, a phenomenon which the authors conjecture holds in general.