2
$\begingroup$

$\DeclareMathOperator{\field}{\mathbb{F}}$ Let $n$ be a positive integer, and let $q : \field_2^{n} \rightarrow \field_2$ be a quadratic form, specified in coordinates as

$$q(x)=\sum_{i =1}^n \alpha_i x_i + \sum_{\substack{j,k=1\\ j<k}}^n \beta_{j,k} x_j x_k$$

for some $\alpha_i, \beta_{j,k} \in \field_2$. For each integer $a\in \{0,\dots, n\}$, I am interested in the quantity

$$ C_{q,a}=\sum_{\substack{x \in \field_2^{n}\\ |x|=a}} (-1)^{q(x)} \in \mathbb{Z},$$

where $|x|$ denotes the Hamming weight of $x$.

Is there a simple formula for $C_{q,a}$? Have these quantities $C_{q,a}$ been studied before?

Improve this question
$\endgroup$
5
  • $\begingroup$ Somewhat relevant paper: Algorithms for Modular Counting of Roots of Multivariate Polynomials $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2021 at 2:16
  • $\begingroup$ (sign corrected) We can compute $C_{q,a}\bmod4$ by considering $q(x)$ as a function over integers, and noticing that $(−1)^{q(x)}\equiv1+2q(x)\pmod4$. Then we have $$C_{q,a}\equiv \binom{n}{a} + 2\binom{n-1}{a-1}\sum_i \alpha_i + 2\binom{n-2}{a-2} \sum_{j<k} \beta_{j,k} \pmod{4}.$$ $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2021 at 14:44
  • $\begingroup$ Thank you! Do you have any intuition for the general question? I would also be interested if you know of a well-behaved, (hopefully "small") family of $\mathbb{Z}$-valued functions on $\{0,1,\dots, n\}$ that these $C_{q,\cdot}$ must lie in. $\endgroup$
    – Ben
    Commented Aug 19, 2021 at 20:05
  • $\begingroup$ My intuition only tells me that computing $C_{q,a}$ may be hard. $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2021 at 21:38
  • $\begingroup$ In fact, $C_{n,a}$ can be similarly computed modulo $2^m$ for $m>2$, although formulas become cumbersome as $m$ grows. So, while in principle taking $2^m>\binom{n}a$ can reveal the value of $C_{q,a}$ itself, direct computation of $C_{q,a}$ will likely be easier. $\endgroup$
    – Max Alekseyev
    Commented Aug 20, 2021 at 3:51

0

Reset to default

You must log in to answer this question.