% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.8}{23(2)}{2016} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\F}{\mathbb{F}} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\bigabs}[1]{\big\lvert#1\big\rvert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Pairs of quadratic forms over finite fields} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Alexander Pott\\ \small Faculty of Mathematics\\[-0.8ex] \small Otto-von-Guericke University\\[-0.8ex] \small Magdeburg, Germany\\ \small\tt alexander.pott@ovgu.de\\ \and Kai-Uwe Schmidt\\ \small Department of Mathematics\\[-0.8ex] \small Paderborn University\\[-0.8ex] \small Paderborn, Germany\\ \small\tt kus@math.upb.de\\ \and Yue Zhou\thanks{Yue Zhou is partially supported by the National Natural Science Foundation of China (No.~11401579).}\\ \small Department of Mathematics and System Sciences\\[-0.8ex] \small National University of Defense Technology\\[-0.8ex] \small Changsha, China\\ \small Department of Mathematics\\[-0.8ex] \small Augsburg University\\[-0.8ex] \small Augsburg, Germany\\ \small\tt yue.zhou.ovgu@gmail.com } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 30, 2014}{Mar 29, 2016}{Apr 15, 2016}\\ \small Mathematics Subject Classifications: 05E15, 05E30, 06E30} \begin{document} \maketitle \begin{abstract} Let $\F_q$ be a finite field with $q$ elements and let $X$ be a set of matrices over~$\F_q$. The main results of this paper are explicit expressions for the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank~$r$, $B$ has rank $s$, and $A+B$ has rank $k$ in the cases that (i) $X$ is the set of alternating matrices over $\F_q$ and (ii) $X$ is the set of symmetric matrices over $\F_q$ for odd $q$. Our motivation to study these sets comes from their relationships to quadratic forms. As one application, we obtain the number of quadratic Boolean functions that are simultaneously bent and negabent, which solves a problem due to Parker and Pott. \end{abstract} \section{Introduction} Let $\F_q$ be a finite field with $q$ elements. Let $X$ be a set of matrices of the same size over~$\F_q$ and let $X_k$ contain all matrices in $X$ of rank $k$. Define \begin{equation} N_X(r,s,k)=\bigabs{\{(A,B)\in X_r\times X_s:\,A+B\in X_k\}}, \label{eqn:def_N} \end{equation} which is the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank~$r$, $B$ has rank $s$, and $A+B$ has rank $k$. We are interested in the numbers $N_X(r,s,k)$ when $X$ is the set of $m\times m$ alternating matrices over $\F_q$ and when $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ (recall that a matrix is \emph{alternating} if it is skew-symmetric and its diagonal contains only zeros). Our motivation to study these sets comes from their relationships to quadratic forms over finite fields. Some consequences of our results for quadratic forms are discussed later in this section. \par Our main results are explicit expressions for the numbers $N_X(r,s,k)$, which involve the \emph{$q^2$-binomial coefficient} given by \[ {x\brack k}=\prod_{i=1}^k(q^{2x-2i+2}-1)/(q^{2i}-1) \] for real $x$ and nonnegative integral $k$ (see~\cite{And1976} and~\cite{DelGoe1975}, for example, for elementary properties of these numbers). For now we state our results for the most important case when $r=s=k=m$. The general results are postponed to later sections. \par We begin with the case that $X$ is the set of alternating matrices over~$\F_q$. Recall that every alternating matrix has even rank (see~\cite[Lemma~10]{DelGoe1975}, for example). We have the following result, which holds for finite fields of arbitrary characteristic. \begin{theorem} \label{thm:alt_fullrank} Let $m$ be even and let $X$ be the set of $m\times m$ alternating matrices over $\F_q$. Writing $n=m/2$, we have \[ N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k-1}-1)^2, \] where \[ v=q^{n(n-1)}\prod_{k=1}^n\,(q^{2k-1}-1) \] is the number of nonsingular matrices in $X$. \end{theorem} \par For the symmetric matrices we have the following result for finite fields of odd characteristic. \begin{theorem} \label{thm:sym_fullrank} Let $q$ be an odd prime power and let $X$ be the set of $m\times m$ symmetric matrices over $\F_q$. Write $n=\lfloor (m+1)/2\rfloor$. Then, for odd $m$, we have \[ N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k-1}-1)^2, \] and for even $m$, we have \[ N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k}-q)^2, \] where \[ v=\begin{cases} q^{n(n-1)}\prod\limits_{k=1}^n(q^{2k-1}-1) & \quad\text{for odd $m$}\\[1ex] q^{n(n+1)}\prod\limits_{k=1}^n(q^{2k-1}-1) & \quad\text{for even $m$} \end{cases} \] is the number of nonsingular matrices in $X$. \end{theorem} \par It can be shown that Theorem~\ref{thm:sym_fullrank} also holds for even $q$ and odd $m$. In particular, it can be shown that, if $q$ is even and $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ and $Y$ is the set of $m+1\times m+1$ alternating matrices over $\F_q$, then \[ N_X(m,m,m)=N_Y(m+1,m+1,m+1), \] and so $N_X(m,m,m)$ can be obtained from Theorem~\ref{thm:alt_fullrank}. This follows from a relationship between two association schemes (see~\cite[Section~5]{Sch2010}, for example) and our discussion on association schemes in Section~\ref{sec:general}. We could not prove, but conjecture based on its verification for $m\in\{2,4,6\}$, that Theorem~\ref{thm:sym_fullrank} also holds for even $q$ and even $m$. \par A quadratic form on $\F_q^m$ that is nonsingular is also called \emph{bent} or a \emph{quadratic bent function}. (There is a more general definition~\cite{Car2010a} of the bent property for arbitrary functions from $\F_q^m$ to $\F_q$, which however is not required here.) Recall that there is a one-to-one correspondence between quadratic forms on $\F_q^m$ and $m\times m$ alternating matrices over $\F_q$ if $q=2$ and $m\times m$ symmetric matrices over $\F_q$ if $q$ is odd. Thus, for $q=2$ or odd $q$, a quadratic form on $\F_q^m$ is bent if the corresponding matrix is nonsingular. \par Vector spaces of bent functions are important in cryptography and coding theory (see~\cite{Car2010a} and~\cite{Car2010b}, for example) and $m$-dimensional spaces of bent functions on $\F_p^m$ for odd prime $p$ (also called \emph{planar} functions) are equivalent to commutative semifields of odd characteristic~\cite{CouHen2008}. Our results give the number of $2$-dimensional spaces of quadratic bent functions on $\F_2^m$. A related and more difficult problem is the determination of the number of inequivalent $2$-dimensional spaces of quadratic bent functions on $\F_q^m$. This number is known for odd $q$ and $m\in\{2,3\}$ and equals $1$ in these cases~\cite{Men1977},~\cite{OzbPot2014}. \par A quadratic form on $\F_2^m$ is \emph{negabent} if its associated alternating matrix $M$ is such that $M+I$ is nonsingular, where $I$ is the identity matrix~\cite{ParPot2007} (again there is a more general definition of negabent functions from $\F_2^m$ to $\F_2$~\cite{ParPot2007}, which we do not require here). A quadratic form on $\F_2^m$ is \emph{bent-negabent} if it is simultaneously bent and negabent. Hence bent-negabent quadratic forms on $\F_2^m$ can only exist if $m$ is even. It has been shown in~\cite[Theorem~8]{ParPot2007} that a quadratic form on $\F_2^m$ is bent-negabent if and only if its associated alternating matrix $M$ is such that $M$ and $M+I+J$ are both nonsingular, where $I$ and $J$ are the identity and the all-ones matrix, respectively. \par Let $X$ be the set of $m\times m$ alternating matrices over $\F_2$ and let $X_k$ contain all matrices in $X$ of rank $k$. Since $X_0,X_1,\dots,X_m$ are the fibres of an association scheme (see Sections~\ref{sec:general} and~\ref{sec:alt}), we find by a general property of association schemes that, for fixed $A\in X_r$, the number of $B\in X_s$ such that $A+B\in X_k$ is independent of the particular choice of $A$. Therefore, Theorem~\ref{thm:alt_fullrank} gives the number of bent-negabent quadratic forms, solving a problem due to Parker and Pott~\cite[Problem~2]{ParPot2007}. \begin{corollary} The number of bent-negabent quadratic forms on $\F_2^{2n}$ is \[ \frac{1}{2^n}\sum_{i=0}^{n}(-1)^i\,2^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(2^{2k-1}-1)^2. \] \end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A general method} \label{sec:general} Suppose that $(X,+)$ is an abelian group of matrices over $\F_q$ (which is certainly true when $X$ is the set of $m\times m$ alternating or symmetric matrices over $\F_q$). In this case the numbers $N_X(r,s,k)$ can be computed as follows. Recall that the \emph{characters} of $(X,+)$ are the homomorphisms from $(X,+)$ to the multiplicative group of the complex numbers and form themselves a group, which is isomorphic to $(X,+)$. \begin{lemma} \label{lem:char_sum} Let $(X,+)$ be an abelian group of matrices over $\F_q$ and let $X_k$ contain all matrices in $X$ of rank $k$. Then the numbers defined in~\eqref{eqn:def_N} satisfy \[ N_X(r,s,k)=\frac{1}{\abs{X}}\sum_{\phi}\sum_{A\in X_r}\phi(A)\sum_{B\in X_s}\phi(B)\sum_{C\in X_k}\phi(C), \] where the first sum ranges over all characters $\phi$ of $(X,+)$. \end{lemma} \begin{proof} Indeed, by an elementary property of characters, the sum \[ \frac{1}{\abs{X}}\sum_{\phi}\phi(A+B-C) \] equals $1$ if $A+B=C$ and is zero otherwise. The lemma follows easily from this. \end{proof} \par The computation of the numbers $N_X(r,s,k)$ is particularly simple in the case that $X$ has the structure of a (symmetric) translation scheme, which is an association scheme with additional properties. Let $X_0,X_1,\dots,X_m$ be a partition of $X$. Then $X$ is a \emph{translation scheme} with \emph{fibres} $X_0,X_1,\dots,X_m$ if the following properties are satisfied: \begin{enumerate} \item[(P1)] $X_0$ contains only the identity of $(X,+)$. \item[(P2)] For all $r\in\{1,\dots,m\}$, we have $x\in X_r$ if and only if $-x\in X_r$. \item[(P3)] If $x-y\in X_r$, then the number of $z\in X$ such that $z-y\in X_s$ and $x-z\in X_k$ is a constant $p(r,s,k)$ (called the \emph{intersection numbers}) depending only on $r$, $s$, and $k$, but not on the particular choice of $x$ and $y$. \end{enumerate} We refer to~\cite{Del1973} and~\cite{DelLev1998} for background on association schemes and in particular to~\cite[Section~V]{DelLev1998} for background on translation schemes. \par Let $X_k$ contain all matrices in $X$ of rank $k$ and suppose that $X_0,X_1,\dots,X_m$ are the fibres of a translation scheme. Then by taking $y$ equal to the zero matrix in (P3), it is readily verified that the numbers $N_X(r,s,k)$ can be computed from the intersection numbers $p(r,s,k)$ via \begin{equation} N_X(r,s,k)=\abs{X_r}\cdot p(r,s,k). \label{eqn:N_intersection_numbers} \end{equation} Let $\widehat{X}$ be the group of characters of $(X,+)$. There is a unique partition $\widehat{X}_0,\widehat{X}_1,\dots,\widehat{X}_m$ of $\widehat{X}$ with the property that \begin{equation} \sum_{A\in X_k}\phi(A) \label{eqn:eigenvalue} \end{equation} is constant for each $\phi\in \widehat{X}_i$. The numbers~\eqref{eqn:eigenvalue}, denoted by $P_k(i)$, are the \emph{eigenvalues} of the translation scheme. It then follows from Lemma~\ref{lem:char_sum} that \[ N_X(r,s,k)=\frac{1}{\abs{X}}\,\sum_{i=0}^m\abs{\widehat{X}_i}\;P_r(i)P_s(i)P_k(i), \] which, via~\eqref{eqn:N_intersection_numbers}, gives a well known formula for the intersection numbers (see~\cite[p.~227]{God1993}, for example). Hence, to compute $N_X(r,s,k)$, it is sufficient to know the \emph{multiplicities} $\abs{\widehat{X}_i}$ and the eigenvalues $P_k(i)$ of the translation scheme. \par This principle can be applied for example when $X$ is the set of $m\times n$ matrices over $\F_q$. Without loss of generality, assume that $m\le n$, in which case, $X_0,X_1,\dots,X_m$ are the fibres of an association scheme whose multiplicities and eigenvalues are given in~\cite{Del1978}. The principle can also be applied in the case that $X$ is the set of $m\times m$ alternating matrices over $\F_q$, which is discussed in Section~\ref{sec:alt}. However, in general, the principle cannot be applied in the case that $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ since then (P3) in the definition of a translation scheme does not hold. We can however still apply Lemma~\ref{lem:char_sum} in this case, which we shall do in Section~\ref{sec:sym}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Alternating matrices} \label{sec:alt} Throughout this section, let $X$ be the set of $m\times m$ alternating matrices over $\F_q$ and write \[ n=\bigg\lfloor \frac{m}{2}\bigg\rfloor\quad\text{and}\quad c=q^{\frac{m(m-1)}{2n}}, \] so that $\abs{X}=c^n$. Let $X_k$ contain all matrices in $X$ of rank~$k$. It is well known that $X_0,X_1,\dots,X_m$ are the fibres of a translation scheme~\cite{DelGoe1975}. \par Let $v(k)$ be the cardinality of $X_k$. (It turns out that these numbers are the multiplicities of the translation scheme.) It is known (see~\cite[Theorem~3]{Mac1969}, for example) that $v(k)=0$ for odd $k$ and \begin{equation} v(2i)={n\brack i}\,\prod_{k=0}^{i-1}\,(c-q^{2k}) \label{eqn:v_alt} \end{equation} for each $i\in\{0,\dots,n\}$. Let $A,S\in X$ and write $a_{ij}$ and $s_{ij}$ for their entries, respectively (indexed from $1$ to $m$). Let $\chi$ be a nontrivial character of $(\F_q,+)$ and define $\phi_S:X\to\mathbb{C}$ by \[ \phi_S(A)=\chi\bigg(\sum_{1\le i