Multidimensional convolution matrices and perfect colorings of subspace hypergraphs applied for bent functions and related designs V. N. Potapov, A. A. Taranenko Abstract The main aim of the present paper is to introduce new methods for the study of combinatorial designs related to bent functions. They are based on interpretations of convolution on finite abelian groups as multiplication by a multidimensional matrix and designs as perfect colorings of subspace hypergraphs of 𝔽 2 n \mathbb{F}_{2}^{n} . We establish a correspondence between eigenfunctions of convolution matrices and perfect colorings of subspace hypergraphs, show that perfect colorings of subspace hypergraphs admit a characterization in terms of convolution and that two-valued eigenfunctions of subspace hypergraphs correspond to perfect colorings. As applications, we represent partial difference sets, bent and plateaued Boolean functions, spreads, and strong bent partitions of 𝔽 2 n \mathbb{F}_{2}^{n} as eigenfunctions of convolution matrices and as perfect colorings of subspace hypergraphs. We also find some eigenvalues of convolution matrices over 𝔽 2 n \mathbb{F}_{2}^{n} and 𝔽 3 n \mathbb{F}_{3}^{n} . Keywords: perfect coloring of hypergraph, convolution, eigenvalue and eigenfunction of multidimensional matrix, bent and plateaued functions, partial difference set, strong bent partition MSC2020: 05C15; 15A18; 15A69; 05C50; 05B30; 05B10 1 Introduction Analytical and algebraic approaches are widely applied for the study of combinatorial designs. The analytical approach deals with designs via convolution or the Fourier transform of their indicator functions. Carlet’s monograph [ carle.boolforcrypt ] on Boolean functions can be considered as an example of this methodology. The graph-theoretical approach interprets designs as subsets of vertices in highly symmetrical graphs that have extremal or regularity properties. In the most common setting, designs correspond to perfect colorings (equitable partitions) of graphs. The concept of equitable partitions was introduced by Delsarte in [ dels.assch ] . Perfect colorings of graphs play a significant role in coding theory and the theory of combinatorial designs. Applications of perfect colorings of several graph families for coding theory are surveyed in papers [ our.perfcolorHam , BorRifaZin.compregcodes ] and in Chapter 1 of book [ ShiSole.CRCinDRG ] . The linear-algebraic approach employs tools from linear algebra and spectral theory of ( 2 -dimensional) matrices to derive necessary conditions for the existence of designs. This approach is largely enabled by the property that the spectrum the adjacency matrix of a graph include the spectrum of the parameter (quotient) matrix of any its perfect coloring. Classical results in this direction are Lloyd’s theorem for perfect codes [ lloyd.perfcode ] , the Fisher and Bruck–Ryser–Chowla inequalities for block designs, and the Bierbrauer–Friedman and Rao inequalities for orthogonal arrays. The novelty of this paper is that we treat convolution as multiplication by a 3 -dimensional matrix. This point of view is well known in computer science and applied mathematics (see, for example, [ Hack.tesorconv , PanVenLeib.lintomulti , RakhOsel.fastconv ] ), but appears to be uninvestigated in modern algebraic hypergraph theory and the theory of combinatorial designs. One of the main objectives of our work is to fill this gap. We also show that this correspondence allows some designs to be linked to eigenfunctions of the convolution matrix and to be represented as perfect colorings of a highly symmetric (subspace) hypergraph. Several notions of eigenvalues and eigenfunctions for hypergraphs have been proposed in the literature. In this paper, we adopt the definition based on eigenvalues and eigenfunctions of the multidimensional adjacency matrix (tensor) of a hypergraph. This approach was introduced by Lim [ lim.eigentensor ] and further developed for symmetric tensors by Qi [ qi.eigentensor ] . It relies on the theory of determinants of multidimensional matrices and resultants of multilinear systems developed in book [ GeKaZe.multdet ] by Gelfand, Kapranov, and Zelevinsky. The concept and properties of perfect colorings of hypergraphs were studied in depth by Taranenko [ my.hyperperfcolor ] . To the best of our knowledge, paper [ PotAv.hypercolor ] (see also preprint ArXiv:2403.02904 for a corrected version) is the only work that directly investigates the relationship between designs and perfect colorings of hypergraphs. In that paper, it was initiated the representation of bent functions and partial difference sets as perfect colorings. In particular, it was shown that transversals in hypergraphs are perfect colorings. The present study continues and extends this line of research, opening the possibility of deriving new conditions for the existence of designs with the help of the spectral theory of multidimensional matrices, and laying the groundwork for applying algebraic hypergraph theory to the study of combinatorial designs. The paper is organised as follows. In Section 2 , we give the main definitions and necessary preliminary results. In particular, we define multidimensional convolution matrices and the subspace hypergraphs \mathcal{H}_{n} and \mathcal{D}_{n} for the space \mathbb{F}_{2}^{n} . We also recall some properties of perfect colorings of hypergraphs, eigenvalues of multidimensional matrices, and the Fourier transform. The main part of the paper starts in Section 3 , where we find some eigenvalues of the convolution matrices for additive groups of the spaces \mathbb{F}_{2}^{n} and \mathbb{F}_{3}^{n} . The spectral properties of the convolution matrix of the additive group of the space \mathbb{F}_{2}^{n} are extremely important due to their relation to combinatorial designs: if the spectrum of the convolution matrix does not contain an eigenvalue corresponding to some design, then such designs do not exist. We suppose that a complete description of the eigenspectrum of convolution matrices for \mathbb{F}_{2}^{n} is an important open problem. In Section 4 , we establish general connections between convolution matrices, subspace hypergraphs, and perfect colorings. In particular, we show that multiplication by the convolution matrix and multiplication by the adjacency matrix of a hypergraph are closely related. This property allows us to express some eigenvectors of one matrix by means of the other. Next, we prove that the definition of a perfect coloring of a subset hypergraph \mathcal{H}_{n} can be given in terms of convolution. At the end of the section, we introduce totally regular hypergraphs, generalizing subspace graphs, and show that every two-valued eigenfunction of totally regular hypergrpahs is a perfect coloring. Finally, Section 5 is devoted to applications of these methods to several designs closely related to bent functions. First, we prove that every partial difference set gives rise to an eigenfunction of the convolution matrix and that it is in one-to-one correspondence with a perfect coloring of a subspace hypergraph with certain parameters. Next, we show that plateaued and bent functions correspond to eigenfunctions of convolution matrices and to perfect colorings of subspace hypergraphs. We conclude the section by proving that every n/2 -spread in \mathbb{F}_{2}^{n} is equivalent to a perfect coloring of a subspace hypergraph with certain parameters, and that every strong bent partition of \mathbb{F}_{2}^{n} is a perfect coloring. 2 Definitions and preliminaries A hypergraph \mathcal{G} is a pair of sets (X,E) , where X is called the set of vertices and E is the set of hyperedges ; each e\in E is a (nonempty) subset of X . A vertex x\in X is said to be incident to a hyperedge e if x\in e . The degree of a vertex x\in X is the number of hyperedges e containing x . If all vertices of \mathcal{G} have degree r , then the hypergraph \mathcal{G} is said to be r -regular . A hypergraph \mathcal{G} is d -uniform if every hyperedge of \mathcal{G} consists of d vertices. Simple graphs are exactly 2 -uniform hypergraphs. In what follows, we use the notation \mathbb{F}_{2}^{n} for an n -dimensional vector space over the prime field \mathbb{F}_{2} , as well as for the additive group of this space. The neutral element of \mathbb{F}_{2}^{n} with respect to addition is \overline{0}=(0,\ldots,0) . A subset L\subseteq\mathbb{F}_{2}^{n} is a linear subspace if for all x,y\in L we have x+y\in L , and a subset U\subseteq\mathbb{F}_{2}^{n} is an affine subspace if there exists a linear subspace L and x\in\mathbb{F}_{2}^{n} such that U=x+L . Let the 3 -uniform subspace hypergraph \mathcal{H}_{n} be the hypergraph with vertex set \mathbb{F}^{n}_{2}\setminus\{\overline{0}\} and hyperedges \{x,y,z\} such that x+y+z=\overline{0} . We also define the 4 -uniform subspace hypergraph \mathcal{D}_{n} with the vertex set \mathbb{F}^{n}_{2} and hyperedges \{x,y,z,v\} such that x+y+z+v=\overline{0} . Note that the hyperedges of \mathcal{H}_{n} correspond to 2 -dimensional linear subspaces of the vector space \mathbb{F}^{n}_{2} without \overline{0} , while the hyperedges of \mathcal{D}_{n} correspond to 2 -dimensional affine subspaces of \mathbb{F}^{n}_{2} . A d -dimensional matrix A of order n is an array (a_{\textbf{x}})_{\textbf{x}\in X^{d}} whose entries a_{\textbf{x}}\in\mathbb{R} are indexed by d -tuples \textbf{x}=(x_{1},\ldots,x_{d}) from the index set X^{d} , where each x_{i} belongs to a set X of cardinality n . 2 -dimensional matrices are standard matrices used in linear algebra, 1 -dimensional matrices are vectors. We often regard 1 -dimensional matrices (vectors) as functions f:X\rightarrow\mathbb{R} and use notation f(x) instead of f_{x} . The adjacency matrix M(\mathcal{G}) of a d -uniform hypergraph \mathcal{G}(X,E) on n vertices is a d -dimensional matrix of order n in which entries m_{\textbf{x}}=\frac{1}{(d-1)!} if \textbf{x}=(x_{1},\ldots,x_{d}) is a hyperedge in \mathcal{G} , and all other entries m_{\textbf{x}} are equal to 0 . Let us introduce several operations for multidimensional matrices. Given a d -dimensional matrix A of order n and d-1 vectors (functions) f_{1},\ldots,f_{d-1} of length n , define the combined product A\cdot(f_{1},\ldots,f_{d-1}) to be the vector f of length n with entries f(x)=\sum\limits_{x_{1},\ldots,x_{d-1}=1}^{n}a_{x,x_{1},\ldots,x_{d-1}}f_{1}(x_{1})\cdots f_{d-1}(x_{d-1}). Note that if for all 2\leq i,j\leq d entries of the matrix A remain unchanged under transpositions (x_{i},x_{j}) in indices, then the combined product A\cdot(f_{1},\ldots,f_{d-1}) does not depend on the order of the vectors f_{1},\ldots,f_{d-1} . In particular, this holds for the adjacency matrices of hypergraphs. Let A be a d -dimensional matrix of order n and let B be a t -dimensional matrix of the same order. Define the product A\circ B to be the ((d-1)(t-1)+1) -dimensional matrix C of order n with entries c_{x,\textbf{y}^{2},\ldots,\textbf{y}^{d}}=\sum\limits_{x_{2}=1}^{n}\cdots\sum\limits_{x_{d}=1}^{n}a_{x,x_{2},\ldots,x_{d}}\cdot b_{x_{2},\textbf{y}^{2}}\cdots b_{x_{d},\textbf{y}^{d}}, where indices \textbf{y}^{2},\ldots,\textbf{y}^{d}\in X^{t-1} and x\in X . In particular, if A is a d -dimensional matrix of order n and f is a vector of length n , then the combined product A\cdot(f,\ldots,f) of d-1 copies of f coincides with the product A\circ f . We say that \theta\in\mathbb{C} is an eigenvalue of a d -dimensional matrix of order n if there exists a eigenvector (or eigenfunction ) f\neq(0,\ldots,0) such that A\circ f=\theta(\mathbb{I}\circ f) . Here \mathbb{I} is the d -dimensional identity matrix , whose entries satisfy i_{\textbf{x}}=1 if x_{1}=\cdots=x_{d} and i_{\textbf{x}}=0 otherwise. In particular, \mathbb{I}\circ f is a function f^{d-1} . If H is a d -uniform hypergraph with d -dimensional adjacency matrix M , then the eigenvalues of M are called the eigenvalues of H , and the eigenvectors of M are called the eigenvectors of H . Following [ my.hyperperfcolor ] , we provide several results on perfect colorings of hypergraphs. Let \mathcal{G}(X,E) be a hypergraph. A surjective function f:X\rightarrow C , where |C|=k , is called a coloring of \mathcal{G} into k colors (or a k -coloring ). Unless otherwise specified, the set of colors C is \{1,\ldots,k\} . A coloring f determines a partition P=(P_{1},\ldots,P_{k}) of the vertex set X , where P_{i}=\{x\in X:f(x)=i\} . Given a coloring f and a hyperedge e , the color range f(e) is the multiset of colors of vertices incident to e : f(e)=\{f(x)|x\in e\} . A coloring f of a hypergraph \mathcal{G} is said to be perfect if for every pair of vertices x and y of the same color, the multisets \{f(e)|x\in e\} and \{f(e)|y\in e\} of color ranges of incident hyperedges coincide. The partition (P_{1},\ldots,P_{k}) corresponding to a perfect coloring f is called an equitable partition. Equivalently, a coloring is perfect if and only if, for every color range \textbf{i}=\{i_{1},i_{2},\ldots,i_{d}\} , the number of hyperedges of color range \mathbf{i} incident to a vertex x of color i_{1} does not depend on the choice of x . We denote these numbers by v_{i_{1},\textbf{i}} . For every k -coloring f of a hypergraph \mathcal{G}(X,E) on n vertices, we define the color matrix F of size n\times k such that the (x,i) -entry of F equals 1 if f(x)=i and equals 0 otherwise. In particular, the i -th column F_{i} of F is the indicator function of the color i , F=(F_{1},\ldots,F_{k}) . We often identify a coloring f with its color matrix F . The following matrix characterization of perfect colorings of hypergraphs and the definition of the parameter matrix of a perfect coloring were given in [ my.hyperperfcolor ] . Theorem 1 . [ my.hyperperfcolor , Theorem 3.4] Let \mathcal{G} be a d -uniform hypergraph with d -dimensional adjacency matrix M . Then a coloring F of \mathcal{G} into k colors is perfect if and only if there exists the d -dimensional parameter matrix S of order k such that M\circ F=F\circ S . Moreover, the entries s_{\textbf{i}} , \textbf{i}=(i_{1},i_{2},\ldots,i_{d}) , of S are given by s_{\textbf{i}}=v_{i_{1},\textbf{i}}\cdot{d-1\choose d_{1},\ldots,d_{k}}^{-1}, where every color j appears in the multiset \{i_{2},\ldots,i_{d}\} exactly d_{j} times, and {d-1\choose d_{1},\ldots,d_{k}}=\frac{(d-1)!}{d_{1}!\cdots d_{k}!} is the multinomial coefficient. This theorem implies the following necessary condition on the existence of perfect colorings in hypergraphs: if there exists a perfect coloring of a hypergraph with the parameter matrix S , then each eigenvalue of S is an eigenvalue of the adjacency matrix of the hypergraph . Proposition 1 . [ my.hyperperfcolor , Theorem 3.11] Let \mathcal{G} be a d -uniform hypergraph with adjacency matrix M . If F is a perfect coloring of \mathcal{G} with the parameter matrix S , then for every eigenvalue \theta and corresponding eigenvector g for the matrix S , there exists the same eigenvalue \theta and eigenvector Fg of the matrix M . Finally, we introduce the convolution matrix and recall some properties of the Fourier transform. Let G be an abelian group of order n . For a subset V\subseteq G , let \chi_{V} denote the indicator function of V : \chi_{V}(x)=1 if x\in V and \chi_{V}(x)=0 otherwise. If V=\{x\} , then we write \chi_{x} instead of \chi_{\{x\}} . Let 1 be the all-one function on G : \textbf{1}(x)=1 for all x\in G . Given functions f,g:G\rightarrow\mathbb{C} , their convolution is defined by (f*g)(x)=\sum\limits_{y\in G}f(y)g(x-y). Define the convolution matrix A_{G} of the group G to be the 3 -dimensional (0,1) -matrix of order n with entries a_{x,y,z}=1 if x=y+z and a_{x,y,z}=0 otherwise. Similarly, we define the t -times convolution matrix A^{(t)}_{G} of the group G to be the (t+2) -dimensional (0,1) -matrix of order n such that a_{\textbf{x}}=1 if and only if x_{1}=x_{2}+\cdots+x_{t+2} . In particular, the convolution matrix is the 1 -times convolution matrix, that is A_{G}^{(1)}=A_{G} . We also note that the set of nonzero entries of the matrix A^{(t)}_{G} forms a linear n -ary MDS code of length t+2 and distance 2 . If G is the additive group of the space \mathbb{F}_{2}^{n} , we denote the convolution matrices as A and A^{(t)} instead of A_{\mathbb{F}_{2}^{n}} and A^{(t)}_{\mathbb{F}_{2}^{n}} . A function f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2} is called a Boolean function. Define the Fourier transform of a Boolean function f to be \widehat{f}(x)=\frac{1}{2^{n/2}}\sum\limits_{z\in\mathbb{F}_{2}^{n}}(-1)^{f(z)+(x,z)}, where (x,z)=x_{1}z_{1}+\cdots+x_{n}z_{n} . We will also need the following well-known properties of the Fourier transform that can be found, for example, in [ carle.boolforcrypt ] . Proposition 2 . 1. \widehat{\widehat{f}}=f for every Boolean function f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2} . 2. \widehat{f+g}=\widehat{f}+\widehat{g} for all Boolean functions f,g:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2} . 3. \widehat{f*g}=2^{n/2}(\widehat{f}\cdot\widehat{g}) for all Boolean functions f,g:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2} . 4. \widehat{\textbf{1}}=2^{n/2}\chi_{\overline{0}} and \widehat{\chi_{\overline{0}}}=\frac{1}{2^{n/2}}\textbf{1} for functions 1 and \chi_{\overline{0}} over \mathbb{F}_{2}^{n} . 5. If U\subseteq\mathbb{F}_{2}^{n} is a linear subspace of dimension k in \mathbb{F}_{2}^{n} , then \widehat{\chi_{U}}=2^{k-n/2}\chi_{U^{\perp}} , where U^{\perp}=\{x\in\mathbb{F}_{2}^{n}:(x,y)=0\mbox{ for all }y\in Y\} . 3 Eigenvalues of convolution matrices of \mathbb{F}_{2}^{n} and \mathbb{F}_{3}^{n} In this section, we find some eigenvalues of the convolution matrices of the groups \mathbb{F}_{2}^{n} and \mathbb{F}_{3}^{n} with the help of their characteristic polynomials and the Kronecker product. Qi [ qi.eigentensor ] proved that for every d -dimensional matrix A of order n , there exists a characteristic polynomial \varphi_{A} of degree n(d-1)^{n-1} such that a number \theta\in\mathbb{C} is an eigenvalue of A if and only if \theta is a root of \varphi_{A} . The existence of such a polynomial is based on the theory of determinants of multidimensional matrices and resultants of multilinear systems developed by Gelfand, Kapranov, and Zelevinsky in [ GeKaZe.multdet ] . If A is a d -dimensional matrix of order n_{1} and B is a d -dimensional matrix of order n_{2} , then the Kronecker product A\otimes B of matrices A and B is the d -dimensional matrix C of order n_{1}n_{2} with entries c_{\textbf{z}}=a_{\textbf{x}}b_{\textbf{y}}, where z_{i}=(x_{i}-1)n_{2}+y_{i} for each i=1,\ldots,d . In particular, if A and B are matrices whose entries are 0 and 1 , then their Kronecker product is also a (0,1) -matrix C whose 1 -entries have indices ((x_{1}-1)n_{2}+y_{1},\ldots,(x_{d}-1)n_{2}+y_{d}) for which a_{x_{1},\ldots,x_{d}}=1 and b_{y_{1},\ldots,y_{d}}=1 . It can be verified by induction that the convolution matrix A_{\mathbb{F}_{p}^{n}} of \mathbb{F}_{p}^{n} is the Kronecker product of n copies of the convolution matrix A_{\mathbb{F}_{p}} . The following result on eigenvalues of the Kronecker product of matrices was proved in [ shao.tensprod ] . Proposition 3 . [ shao.tensprod , Theorem 3.4] Let A be a d -dimensional matrix of order n_{1} and let B be a d -dimensional matrix of order n_{2} . If \theta is an eigenvalue of A and \theta^{\prime} is an eigenvalue of B , then \theta\theta^{\prime} is an eigenvalue of the Kronecker product A\otimes B . Using this property, we find some eigenvalues of the convolution matrix A_{\mathbb{F}_{2}^{n}} . Theorem 2 . Let A_{\mathbb{F}_{2}^{n}} be the 3 -dimensional convolution matrix of \mathbb{F}_{2}^{n} . Then for all nonnegative integers k_{0},k_{1},k_{2} with k_{0}+k_{1}+k_{2}\leq n , the value 2^{k_{0}-k_{1}-k_{2}}(-1+i\sqrt{7})^{k_{1}}(-1-i\sqrt{7})^{k_{2}} is an eigenvalue of A_{\mathbb{F}_{2}^{n}} . Proof. Recall that the convolution matrix A_{\mathbb{F}_{2}^{n}} is the n -times Kronecker product of the matrix A_{\mathbb{F}_{2}} . The convolution matrix A_{\mathbb{F}_{2}} of \mathbb{F}_{2} is a 3 -dimensional matrix of order 2 of the form A_{\mathbb{F}_{2}}=\left(\begin{array}[]{cc|cc}1&0&0&1\\ 0&1&1&0\end{array}\right). Using the calculation of Morozov and Shakirov [ MorShak.resultform ] for the resultant of a system of equations given by an arbitrary 3 -dimensional matrix of oder 2 , we find the characteristic polynomial \varphi(\theta)=Res(A-\theta\mathbb{I}) of A_{\mathbb{F}_{2}} : \varphi(\theta)=\theta^{4}-2\theta^{3}+\theta^{2}-4\theta+4=(1-\theta)(2-\theta)(\theta^{2}+\theta+2). Consequently, the matrix A_{\mathbb{F}_{2}} has eigenvalues 1 , 2 , and \frac{1}{2}(-1\pm i\sqrt{7}) . Thus, by Proposition 3 , the convolution matrix A_{\mathbb{F}_{2}^{n}} has eigenvalues 2^{k_{0}-k_{1}-k_{2}}(-1+i\sqrt{7})^{k_{1}}(-1-i\sqrt{7})^{k_{2}} for all nonnegative integers k_{0},k_{1},k_{2} such that k_{0}+k_{1}+k_{2}\leq n . ∎ Acting similarly, we find some eigenvalues of the convolution matrix A_{\mathbb{F}_{3}^{n}} . Theorem 3 . Let A_{\mathbb{F}_{3}^{n}} be the 3 -dimensional convolution matrix of \mathbb{F}_{3}^{n} . Then for all nonnegative integers k_{0},k_{1},k_{2} with k_{0}+k_{1}+k_{2}\leq n , the value 3^{k_{0}}(i\sqrt{3})^{k_{1}}(-i\sqrt{3})^{k_{2}} is an eigenvalue of A_{\mathbb{F}_{3}^{n}} . Proof. As in the previous proof, A_{\mathbb{F}_{3}^{n}} is the n -times Kronecker product of the matrix A_{\mathbb{F}_{3}} . The convolution matrix A_{\mathbb{F}_{3}} of \mathbb{F}_{3} has the form A_{\mathbb{F}_{3}}=\left(\begin{array}[]{ccc|ccc|ccc}1&0&0&0&0&1&0&1&0\\ 0&0&1&0&1&0&1&0&0\\ 0&1&0&1&0&0&0&0&1\\ \end{array}\right). Let \mathcal{E} denote the adjacency matrix of the 3 -uniform hypergraph H on 3 vertices with a single hyperedge: \mathcal{E}=\left(\begin{array}[]{ccc|ccc|ccc}0&0&0&0&0&\nicefrac{{1}}{{2}}&0&\nicefrac{{1}}{{2}}&0\\ 0&0&\nicefrac{{1}}{{2}}&0&0&0&\nicefrac{{1}}{{2}}&0&0\\ 0&\nicefrac{{1}}{{2}}&0&\nicefrac{{1}}{{2}}&0&0&0&0&0\\ \end{array}\right). Note that A_{\mathbb{F}_{3}}=2\mathcal{E}+\mathbb{I} . Since the characteristic polynomial \varphi_{A_{\mathbb{F}_{3}}}(\theta) of A_{\mathbb{F}_{3}} is the resultant of the system (A_{\mathbb{F}_{3}}-\theta\mathbb{I})f=0 (see [ qi.eigentensor ] ), \varphi_{A_{\mathbb{F}_{3}}} can be obtained from the characteristic polynomial \varphi_{2\mathcal{E}}(\theta) of 2\mathcal{E} by replacing \theta with \theta-1 . The characteristic polynomial \varphi_{\mathcal{E}}(\theta) for the adjacency matrix \mathcal{E} was found in [ CoopDut.hyperspec ] by Cooper and Dutle: \varphi_{\mathcal{E}}(\theta)=\theta^{3}(\theta^{3}-1)^{3}=\theta^{3}(\theta-1)^{3}(\theta^{2}+\theta+1)^{3}. The eigenvalues of the matrix 2\mathcal{E} are those of \mathcal{E} multiplied by 2 . Consequently, its characteristic polynomial is \varphi_{2\mathcal{E}}(\theta)=\theta^{3}(\theta-2)^{3}(\theta^{2}+2\theta+4)^{3}. Replacing \theta with \theta-1 , we obtain \varphi_{A_{\mathbb{F}_{3}}}(\theta)=(\theta-1)^{3}(\theta-3)^{3}(\theta^{2}+3)^{3}. Thus 1 , 3 , and \pm i\sqrt{3} are the eigenvalues of A_{\mathbb{F}_{3}} . By Proposition 3 , the convolution matrix A_{\mathbb{F}_{3}^{n}} has eigenvalues 3^{k_{0}}(i\sqrt{3})^{k_{1}}(-i\sqrt{3})^{k_{2}} for all nonnegative integers k_{0},k_{1},k_{2} such that k_{0}+k_{1}+k_{2}\leq n . ∎ 4 Relations between convolution matrices, subspace hypergraphs, and perfect colorings We begin this section by showing that the convolution of functions coincides with the combined product of these functions and the convolution matrix. Lemma 1 . Let G be a finite abelian group, let A^{(t)}_{G} be the t -times convolution matrix of the group G , and let f_{1},\ldots,f_{t+1}:G\rightarrow\mathbb{C} . Then A^{(t)}_{G}\cdot(f_{1},\ldots,f_{t+1})=f_{1}*\cdots*f_{t+1}. Proof. From the definition of convolution, for each x\in G we have (f_{1}*\cdots*f_{t+1})(x)=\sum\limits_{x_{1},\ldots,x_{t}\in G}f_{1}(x_{1})\cdots f_{t}(x_{t})\cdot f_{t+1}(x-x_{1}-\ldots-x_{t}). Using the definition of the combinded product and the fact that the entry a_{x_{0},x_{1},\ldots x_{t+1}} of the convolution matrix A^{(t)}_{G} is equal to 1 if and only if x_{0}=x_{1}+\cdots+x_{t+1} in G , we obtain \displaystyle A^{(t)}_{G}\cdot(f_{1},\ldots,f_{t+1})(x)=\sum\limits_{x_{1},\ldots,x_{t+1}\in G}a_{x,x_{1},\ldots,x_{t+1}}f_{1}(x_{1})\cdots f_{t+1}(x_{t+1})= \displaystyle\sum\limits_{x_{1},\ldots,x_{t}\in G}f_{1}(x_{1})\cdots f_{t}(x_{t})\cdot f_{t+1}(x-x_{1}-\ldots-x_{t})=(f_{1}*\ldots*f_{t+1})(x). ∎ Since the combined product A\cdot(f,\ldots,f) of a multidimensional matrix A and a functions f coincides with the product A\circ f , we obtain the following property. Corollary 1 . Let G be a finite abelian group, let f:G\rightarrow\mathbb{C} , and let A^{(t)}_{G} be the t -times convolution matrix of the group G . Then A^{(t)}_{G}\circ f=f*\cdots*f , that is, the convolution of t+1 copies of the function f . We also show that the product of convolution matrices is a convolution matrix of higher dimension. Proposition 4 . If A^{(t)}_{G} and A^{(s)}_{G} are t -times and s -times convolution matrices of a finite abelian group G , respectively, then A^{(t)}_{G}\circ A^{(s)}_{G}=A^{(ts+t+s)}_{G} . In particular, A^{(1)}_{G}\circ A^{(1)}_{G}=A^{(3)}_{G} . Proof. By the definition of the product of multidimensional matrices, A^{(t)}_{G}\circ A^{(s)}_{G} is a (ts+t+s+2) -dimensional matrix C with entries c_{x,\textbf{y}^{2},\ldots,\textbf{y}^{t+2}}=\sum\limits_{x_{2}=1}^{n}\cdots\sum\limits_{x_{t+2}=1}^{n}a^{(t)}_{x,x_{2},\ldots,x_{t+2}}\cdot a^{(s)}_{x_{2},\textbf{y}^{2}}\cdots a^{(s)}_{x_{t+2},\textbf{y}^{t+2}}, where indices \textbf{y}^{2},\ldots,\textbf{y}^{t+2}\in G^{s+1} have length s+1 and x\in G . By the definition of the convolution matrices, a^{(t)}_{x,x_{2},\ldots,x_{t+2}}=1 if x=x_{2}+\cdots+x_{t+2} and a^{(t)}_{x,x_{2},\ldots,x_{t+2}}=0 otherwise, and for all i\in\{2,\ldots,t+2\} we have that a^{(s)}_{x_{i},\textbf{y}^{i}}=1 if x_{i}=y^{i}_{1}+\cdots+y^{i}_{s+1} and a^{(s)}_{x_{i},\textbf{y}^{i}}=0 otherwise. Consequently, c_{x,\textbf{y}^{2},\ldots,\textbf{y}^{t+2}}=1 if x=y^{2}_{1}+\cdots+y^{2}_{s+1}+\cdots+y^{t+2}_{1}+\cdots+y^{t+2}_{s+1} and c_{x,\textbf{y}^{2},\ldots,\textbf{y}^{t+2}}=0 otherwise, that is equivalent to that A^{(t)}_{G}\circ A^{(s)}_{G}=A^{(ts+t+s)}_{G} . ∎ Next, we express the combined product of functions and convolution matrices with the help of their combined product by the adjacency matrices of the subspace hypergraphs \mathcal{H}_{n} and \mathcal{D}_{n} . Proposition 5 . Let A be the convolution matrix of \mathbb{F}_{2}^{n} , let M_{H} be the adjacency matrix of the subspace hypergraph \mathcal{H}_{n} , f,g:\mathbb{F}_{2}^{n}\rightarrow\mathbb{C} , and let f^{\prime} and g^{\prime} be the restrictions of f and g to \mathbb{F}_{2}^{n}\setminus\{\overline{0}\} . Then for every x\neq\overline{0} we have (A\cdot(f,g))(x)=2(M_{H}\cdot(f^{\prime},g^{\prime}))(x)+f(\overline{0})g(x)+f(x)g(\overline{0}) and (A\cdot(f,g))(\overline{0})=\sum\limits_{x\in\mathbb{F}_{2}^{n}}f(x)g(x). Proof. By the definition of the convolution matrix, a_{x,y,z}=1 if x=y+z , and a_{x,y,z}=0 otherwise. Note that in the group \mathbb{F}_{2}^{n} it holds x=-x for all x , and the equality x+y=\overline{0} is equivalent to x=y . Then for all x\neq\overline{0} we have \displaystyle(A\cdot(f,g))(x)=\sum\limits_{y,z\in\mathbb{F}_{2}^{n}}a_{x,y,z}f(y)g(z)=\sum\limits_{y\in\mathbb{F}_{2}^{n}}f(y)g(x+y)= \displaystyle\sum\limits_{y\neq\overline{0},x}f(y)g(x+y)+f(\overline{0})g(x)+f(x)g(\overline{0})=2(M_{H}\cdot(f^{\prime},g^{\prime}))(x)+f(\overline{0})g(x)+f(x)g(\overline{0}). If x=\overline{0} , then (A\cdot(f,g))(\overline{0})=\sum\limits_{x,y\in\mathbb{F}_{2}^{n}}a_{\overline{0},x,y}f(x)g(y)=\sum\limits_{x\in\mathbb{F}_{2}^{n}}f(x)g(x). ∎ Corollary 2 . Let A be the convolution matrix of \mathbb{F}_{2}^{n} , M_{H} be the adjacency matrix of the subspace hypergraph \mathcal{H}_{n} , f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{C} , and let f^{\prime} be the restriction of f to \mathbb{F}_{2}^{n}\setminus\{\overline{0}\} . • If f is an eigenvector of A corresponding to an eigenvalue \theta and f(\overline{0})=0 , then f^{\prime} is an eigenvector for M_{H} with an eigenvalue \theta/2 . • If f is an eigenvector of A corresponding to an eigenvalue \theta and f:\mathbb{F}_{2}^{n}\rightarrow\{0,1\} , then f^{\prime} is an eigenvector for M_{H} with an eigenvalue \theta/2-f(\overline{0}) . Proof. If f is an eigenfunction of A corresponding to an eigenvalue \theta , then A\circ f=\theta(\mathbb{I}\circ f) , where \mathbb{I} is the 3 -dimensional identity matrix. From Proposition 5 , for every x\neq\overline{0} we have A\circ f(x)=2(M_{H}\circ f^{\prime})(x)+2f(\overline{0})f(x). Hence, M_{H}\circ f^{\prime}=\theta/2(\mathbb{I}\circ f^{\prime})-f(\overline{0})f^{\prime}. If f(\overline{0})=0 , then \theta/2 is the eigenvalue of M_{H} for the eigenfunction function f^{\prime} . Since for each x\neq\overline{0} we have (\mathbb{I}\circ f^{\prime})(x)=(f^{\prime}(x))^{2} , this value coincides with f^{\prime}(x) if and only if f^{\prime}(x) is equal to 0 or 1 . Consequently, if f takes only values 0 and 1 , then f^{\prime} is the eigenfunction of M_{H} corresponding to the eigenvalue \theta/2-f(\overline{0}) . ∎ We obtain a similar result for the 2 -times convolution matrix and the adjacency matrix of the subspace hypergraph \mathcal{D}_{n} . Proposition 6 . Let A^{(2)} be the 2 -times convolution matrix of \mathbb{F}_{2}^{n} , M_{D} be the adjacency matrix of the subspace hypergraph \mathcal{D}_{n} , and let f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{C} . Then for all x\in\mathbb{F}_{2}^{n} we have (A^{(2)}\circ f)(x)=6(M_{D}\circ f)(x)+3(\sum\limits_{y\neq x}f^{2}(y))f(x)+(\mathbb{I}\circ f)(x). Proof. By the definition of the 2 -times convolution matrix A^{(2)} , its entry a_{x,y,z,v}=1 if x=y+z+v and a_{x,y,z,v}=0 otherwise. Note that if x,y,z,v\in\mathbb{F}_{2}^{n} satisfy x=y+z+v and two of them coincide (for example, x=y ), then the remaining two elements also coincide ( z=v ). Given x\in\mathbb{F}_{2}^{n} , let R_{x} denote the set of all ordered pairs (y,z) such that x,y,z , and x+y+z are pairwise distinct. Then for every x\in\mathbb{F}_{2}^{n} we have \displaystyle(A^{(2)}\circ f)(x)=\sum\limits_{y,z,v\in\mathbb{F}_{2}^{n}}a_{x,y,z,v}f(y)f(z)f(v)= \displaystyle\sum\limits_{(y,z)\in R_{x}}f(y)f(z)f(x+y+z)+3\sum\limits_{y\neq x}f(y)^{2}f(x)+f^{3}(x)= \displaystyle 6(M_{D}\circ f)(x)+3(\sum\limits_{y\neq x}f^{2}(y))f(x)+(\mathbb{I}\circ f)(x), where \mathbb{I} is the 4 -dimensional identity matrix. ∎ Similarly to Corollary 2 , the above statement can also be used to show that certain eigenfunctions of the 2 -times convolution matrix give rise to eigenfunctions of the subspace hypergraph and vice versa. Next, we use the obtained results to show that perfect colorings of the subspace hypergraph \mathcal{H}_{n} can be described in terms of the convolution of the indicator functions of colors. Lemma 2 . Let M_{H} be the adjacency matrix of the subspace hypergraph \mathcal{H}_{n} . A k -coloring with color matrix F=(F_{1},\ldots,F_{k}) is a perfect coloring of \mathcal{H}_{n} with the parameter matrix S if and only if for all j,\ell\in\{1,\ldots,k\} it holds F_{j}*F_{\ell}=\sum\limits_{i=1}^{k}2s_{i,j,\ell}F_{i} . Proof. Recall that the vertex set of the subspace hypergraph \mathcal{H}_{n} is \mathbb{F}_{2}^{n}\setminus\{\overline{0}\} . Without loss of generality, we extend the indicator functions of the colors F_{i} from \mathbb{F}_{2}^{n}\setminus\{\overline{0}\} to \mathbb{F}_{2}^{n} by setting F_{i}(\overline{0})=0 for all i\in\{1,\ldots,k\} . This modification does not change the value (F_{j}*F_{\ell})(x) for all x\neq\overline{0} . Consider a vertex x\neq\overline{0} of color i in the coloring F . From Lemma 1 and Proposition 5 , for all j,\ell\in\{1,\ldots,k\} (either or both of which may be equal to i ) we have (F_{j}*F_{\ell})(x)=A\cdot(F_{j},F_{\ell})(x)=2(M_{H}\cdot(F_{j},F_{\ell}))(x). If j\neq\ell , then by the definition of the adjacency matrix of \mathcal{H}_{n} and F_{i}(x)=1 , we obtain (M_{H}\cdot(F_{j},F_{\ell}))(x)=\sum\limits_{(y,z):(x,y,z)\in E(\mathcal{H}_{n})}1/2\cdot F_{j}(y)F_{\ell}(z)=v_{i,j,\ell}(x)/2=v_{i,j,\ell}(x)/2\cdot F_{i}(x), where v_{i,j,\ell}(x) denotes the number of hyperedges of color range \{i,j,\ell\} incident to the vertex x , and E(\mathcal{H}_{n}) is the hyperedge set of \mathcal{H}_{n} . By Theorem 1 , the coloring F is perfect if and only if the number v_{i,j,\ell}(x) does not depend on the choice of x and equals 2s_{i,j,\ell} . Similarly, if j=\ell , then (M_{H}\cdot(F_{j},F_{j}))(x)=\sum\limits_{(y,z):(x,y,z)\in E(\mathcal{H}_{n})}1/2\cdot F_{j}(y)F_{j}(z)=v_{i,j,j}(x)=v_{i,j,j}(x)F_{i}(x), where v_{i,j,j}(x) denotes the number of hyperedges of color range \{i,j,j\} incident to x . Again, by Theorem 1 , the coloring F is perfect if and only if the number v_{i,j,j}(x) does not depend on x and equals s_{i,j,j} . Therefore, F is a perfect coloring with the parameter matrix S if and only if for all j,\ell\in\{1,\ldots,k\} it holds F_{j}*F_{\ell}=\sum\limits_{i=1}^{k}2s_{i,j,\ell}F_{i} . ∎ Note that for the 4 -uniform subspace hypergraph \mathcal{D}_{n} one can also state a similar condition for a coloring F to be perfect in terms of the double convolution of F_{j} , F_{\ell} , and F_{m} . However, in that case the coefficients in the linear combinations of F_{i} do not admit such a simple expression. It is well known [ ShiSole.CRCinDRG , Corollary 1.9] that every 2 -valued eigenfunction of a regular graph corresponds to a perfect 2 -coloring. By Theorem 1 , to every perfect 2 -coloring of a uniform hypergraph \mathcal{G} we can associate a 2 -valued eigenfunction of its adjacency matrix M . Indeed, F is the color matrix of a perfect 2 -coloring with the parameter matrix S if and only if M\circ F=F\circ S . Then for every eigenfunction g=(\alpha,\beta) , with \alpha\neq\beta , of the matrix S , the function Fg is a 2 -valued eigenfunction of the matrix M , where the distinct values of Fg correspond to the two colors in the perfect coloring (see also [ my.hyperperfcolor , Theorem 3.10] ). Unlike the graph case, for hypergraphs this statement cannot be naturally reversed. We prove this for the family of totally regular hypergraphs, which includes subspace hypergraphs; the general case remains open. Let \mathcal{G}(X,E) be a d -uniform hypergraph. Given a set S\subseteq X of vertices of \mathcal{G} , the degree deg(S) of S is the number of hyperedges e\in E such that S\subseteq E . We say that a d -uniform hypergraph \mathcal{G} is totally regular (or totally (r_{1},\ldots,r_{d-1}) -regular ) if there exist numbers r_{i}\in\mathbb{N} , i=1,\ldots,d-1 , such that for every subset S of vertices with |S|=i we have deg(S)=r_{i} . Totally regular hypergraphs appear in literature under different names. For example in [ niki.anmethhyper ] , d -unform totally regular hypergraphs are called (d-1) -set regular. Totally regular hypergraphs are in one-to-one correspondence with block designs. A t - (n,k,\lambda) -design is a collection of blocks of size k over a ground set X of size n such that every t -element subset of X is contained in exactly \lambda blocks; t - (n,k,1) -designs are called Steiner systems S(t,k,n) . The hyperedges of a d -uniform totally regular hypergraph on n vertices, with degree of (d-1) -element subsets equal to r_{d-1} , form the blocks of a (d-1) - (n,d,r_{d-1}) -design. In particular, from the divisibility conditions for the parameters of (d-1) - (n,d,r_{d-1}) -designs, it follows that all parameters r_{i} of totally (r_{1},\ldots,r_{d-1}) -regular hypergraphs are propotional to r_{d-1} . The set of hyperedges of the subspace hypergraph \mathcal{H}_{n} forms a linear Steiner triple system S(2,3,2^{n}-1) , and the set of hyperedges of \mathcal{D}_{n} forms a linear Steiner quadruple system S(3,4,2^{n}) . Consequently, the subspace hypergraphs \mathcal{H}_{n} and \mathcal{D}_{n} are totally regular. We are now ready to prove that 2 -valued eigenfunctions of totally regular hypergraphs are their perfect 2 -colorings. Theorem 4 . Let d\geq 3 , and let \mathcal{G}(X,E) be a d -uniform totally (r_{1},\ldots,r_{d-1}) -regular hypergraph on n vertices with the adjacency matrix M . Assume that f is an eigenvector of M corresponding to an eigenvalue \theta such that f(x)\in\{\alpha,\beta\} for all x\in X , where \alpha\neq\beta . Then f is a perfect 2 -coloring of \mathcal{G} . Proof. Consider an arbitrary vertex x of color \alpha . Then the equation (M\circ f)(x)=\theta(\mathbb{I}\circ f)(x) is equivalent to \alpha^{d-1}t_{0}^{x}+\alpha^{d-2}\beta t_{1}^{x}+\cdots+\beta^{d-1}t_{d-1}^{x}=\theta\alpha^{d-1}, (1) where t_{j}^{x} denotes the number of hyperedges e\in E incident to x such that d-j vertices of e have color \alpha and j vertices of e have color \beta . For every j=0,\ldots,d-2 , consider an arbitrary collection of distinct vertices x^{1},\ldots,x^{j} , all different from x and all of color \alpha . Let t_{k}^{x,x^{1},\ldots,x^{j}} denote the number of hyperedges e incident to the vertices x,x^{1},\ldots,x^{j} such that d-k vertices from e have color \alpha and k vertices from e have color \beta . In particular, if d-k|(\mathbb{F}^{n}_{2}\setminus\Gamma)\cap P| . Proof of Claim. Each hyperspace \Gamma in \mathbb{F}^{n}_{2} is uniquely determined by a nonzero orthogonal vector z . Denote \Gamma_{z}=\{x\in\mathbb{F}^{n}_{2}:(x,z)=0\} . By the definition of the Fourier transform, \widehat{{\chi}_{P}}(z)=\frac{1}{2^{n/2}}(|\Gamma_{z}\cap P|-|(\mathbb{F}^{n}_{2}\setminus\Gamma_{z})\cap P|) for z\neq\overline{0} and \widehat{{\chi}_{P}}(\overline{0})=\frac{1}{2^{n/2}}|P| . It is also not hard to see that \sum\limits_{z\in\mathbb{F}^{n}_{2}}\widehat{{\chi}_{P}}(z)=2^{n/2}\cdot{\chi}_{P}(\overline{0})=2^{n/2} . If |P|\neq 2^{n} , then there exists z\neq\overline{0} such that \widehat{{\chi}_{P}}(z)>0 , which implies |\Gamma_{z}\cap P|>|(\mathbb{F}^{n}_{2}\setminus\Gamma_{z})\cap P| . This proves the claim. Returning to the proof of the theorem, let \Gamma_{z} be a hyperspace such that |\Gamma_{z}\cap P|>|(\mathbb{F}^{n}_{2}\setminus\Gamma_{z})\cap P| . Denote p_{1}=|\Gamma_{z}\cap P| and p_{2}=|(\mathbb{F}^{n}_{2}\setminus\Gamma_{z})\cap P| , |P|=p_{1}+p_{2} . If p_{1}=|P| , then P\subseteq\Gamma_{z} , and identifying \Gamma_{z} and \mathbb{F}_{2}^{n-1} , the result follows from the inductive assumption. Suppose now that 0p_{2}>0 , the proof is complete. ∎ 5.4 Bent partitions A partition P=\{U,P_{1},\ldots,P_{K}\} of \mathbb{F}^{n}_{2} is called a normal bent partition of depth K , if every function f satisfying the following properties is bent: 1. For each c\in\{0,1\} , the preimage f^{-1}(c) consists of exactly K/2 sets among P_{1},\dots,P_{K} ; 2. The function f is constant on the set U . The following property of normal bent partitions was proved in [ AnKaMei.bentpart ] . Proposition 9 . [ AnKaMei.bentpart , Lemma 1] Let P=\{U,P_{1},\ldots,P_{K}\} be a normal bent partition of \mathbb{F}^{n}_{2} of depth K . Then K=2^{k} for some k , the set U is an n/2 -dimensional affine subspace of \mathbb{F}^{n}_{2} , and all sets P_{i} , 1\leq i\leq 2^{k} , have the same size: |P_{i}|=\frac{2^{n}-2^{n/2}}{2^{k}} . It is known [ carle.boolforcrypt ] that an affine transformation of the argument of a bent function is again a bent function. Therefore, every affine transformation of \mathbb{F}^{n}_{2} preserves the property of a partition being a normal bent partition. Hence, in what follows we may assume that U is a linear subspace. As noted in [ AnKaMei.bentpart ] , a normal bent partition \{U,P_{1},\ldots,P_{2^{n/2}}\} of \mathbb{F}^{n}_{2} of depth 2^{n/2} is equivalent to an n/2 -spread. However, there exist normal bent partitions of depth 2^{n/2} that are different from spreads [ MeidlPir.bentforspred ] . If a partition R=\{U,R_{1},\ldots,R_{2^{k-m}}\} is obtained from a normal bent partition P=\{U,P_{1},\ldots,P_{2^{k}}\} by uniting arbitrary groups of 2^{m} subsets P_{i} , where m