Let $q$ be a prime power and $\omega=\exp(2\pi i/q)$. For a fixed $y\in\mathbb{Z}_q^n$, the map

$$\mathbb{Z}_q^n\ni x\mapsto \omega^{x\cdot y}=\omega^{x_1y_1+\dots+x_ny_n}$$

is a character of $\mathbb{Z}_q^n$. The Hamming weight $\operatorname{wt}_H$ of $x\in\mathbb{Z}_q^n$ is the number of nonzero entries in $x$. Let $X_i=\{x\in \mathbb{Z}_q^n\mid \operatorname{wt}_H(x)=i\}.$ I want to prove that the sum $\sum_{x\in X_i}\omega^{x\cdot y}$ is constant for all $y\in X_k$. This is true for $q=2$ since the sets $X_i$ are invariant under the group operation of $S_n$ and for all $x,y\in X_k$ there exists $g\in S_n$ such that $gx=y$. Thus, we have

$$\sum_{x\in X_i}\omega^{x\cdot gy}=\sum_{x\in X_i}\omega^{g^{-1}x\cdot y}=\sum_{x\in X_i}\omega^{x\cdot y}.$$

But I don't see that the sum is constant if $q\geq 3$.

EDIT: I think that for $q\geq 3$ we could use a similar argument. If we take the group $S_{q-1}^n\wr S_n$, which operates on $x\in\mathbb{Z}_q^n$ by first permuting the positions of $x$ and then independently permuting the alphabet $\{1,2,\dots,q-1\}$ at each position, the sets $X_i$ should be invariant under this group action. Therefore, the sum should be constant for all $y\in X_k$. But I'm not completely sure that this is the right argument.

  • $\begingroup$ I think that the constancy eventually follows from the fact that $$\sum_{x\in \Bbb{Z}_q, x\neq0}\omega^{xy}=-1$$ whenever $y\neq0$ and equal to $q-1$ if $y=0$. I may be wrong, but I think this constancy is part of the derivation of the properties of Krawtchouk polynomials. I don't have the time to search now, but I'm more than a bit optimistic. $\endgroup$ – Jyrki Lahtonen Aug 16 '18 at 14:23
  • $\begingroup$ Anyway, the sum in my previous comment leads to a calculation where the essential parameter is the size of the intersection of the supports of $x$ and $y$. It also explains why the actual values of the non-zero components of $y$ don't matter - just whether they are non-zero. Unless no one else bites in the interim, I will return to this later tonight. Bridge club session starting in two minutes. $\endgroup$ – Jyrki Lahtonen Aug 16 '18 at 14:28
  • $\begingroup$ @JyrkiLahtonen: It's correct that this constancy is connected to the Krawtchouk polynomials. I want to derive the eigenvalues of the Hamming scheme by using that this scheme is a translation scheme and the eigenvalues of a translation scheme are computed using this sum of characters. $\endgroup$ – user160919 Aug 16 '18 at 15:05
  • $\begingroup$ @JyrkiLahtonen: I see how to prove that this sum is constant by using $$\sum_{x\in \Bbb{Z}_q, x\neq0}\omega^{xy}=-1.$$The proof is a little bit lengthy (see math.stackexchange.com/a/2181124/296687) and thus, I would like to prove the constancy by using a simple symmetry argument. $\endgroup$ – user160919 Aug 16 '18 at 15:23
  • $\begingroup$ I see, I was just typing a comment explaining that something like the group in your edit should work when $q$ is a prime (Actually I think that the group of monomial matrices $\mu_{q-1}\wr S_n$ will do). When $q$ is not a prime, equivalently, when $\Bbb{Z}_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $x\cdot y$ and $x\cdot y'$ with $x$ ranging over $X_i$, when $y$ and $y'$ are two different vectors of the same weight such that one has components coprime to $q$ but the other has components divisible by $p$, $q=p^\ell$. $\endgroup$ – Jyrki Lahtonen Aug 17 '18 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.