Constant sum of characters
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $q$ be a prime power and $omega=exp(2pi i/q)$. For a fixed $yinmathbbZ_q^n$, the map
$$mathbbZ_q^nni xmapsto omega^xcdot y=omega^x_1y_1+dots+x_ny_n$$
is a character of $mathbbZ_q^n$. The Hamming weight $operatornamewt_H$ of $xinmathbbZ_q^n$ is the number of nonzero entries in $x$. Let
$X_i=xin mathbbZ_q^nmid operatornamewt_H(x)=i.$ I want to prove that the sum
$sum_xin X_iomega^xcdot y$ is constant for all $yin 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,yin X_k$ there exists $gin S_n$ such that $gx=y$. Thus, we have
$$sum_xin X_iomega^xcdot gy=sum_xin X_iomega^g^-1xcdot y=sum_xin X_iomega^xcdot y.$$
But I don't see that the sum is constant if $qgeq 3$.
EDIT: I think that for $qgeq 3$ we could use a similar argument. If we take the group $S_q-1^nwr S_n$, which operates on $xinmathbbZ_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 $yin X_k$. But I'm not completely sure that this is the right argument.
abstract-algebra combinatorics finite-fields coding-theory algebraic-combinatorics
asked Aug 16 at 8:38
user160919
19411
 |Â
show 1 more comment
up vote
3
down vote
favorite
Let $q$ be a prime power and $omega=exp(2pi i/q)$. For a fixed $yinmathbbZ_q^n$, the map
$$mathbbZ_q^nni xmapsto omega^xcdot y=omega^x_1y_1+dots+x_ny_n$$
is a character of $mathbbZ_q^n$. The Hamming weight $operatornamewt_H$ of $xinmathbbZ_q^n$ is the number of nonzero entries in $x$. Let
$X_i=xin mathbbZ_q^nmid operatornamewt_H(x)=i.$ I want to prove that the sum
$sum_xin X_iomega^xcdot y$ is constant for all $yin 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,yin X_k$ there exists $gin S_n$ such that $gx=y$. Thus, we have
$$sum_xin X_iomega^xcdot gy=sum_xin X_iomega^g^-1xcdot y=sum_xin X_iomega^xcdot y.$$
But I don't see that the sum is constant if $qgeq 3$.
EDIT: I think that for $qgeq 3$ we could use a similar argument. If we take the group $S_q-1^nwr S_n$, which operates on $xinmathbbZ_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 $yin X_k$. But I'm not completely sure that this is the right argument.
abstract-algebra combinatorics finite-fields coding-theory algebraic-combinatorics
asked Aug 16 at 8:38
user160919
19411
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
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.
– Jyrki Lahtonen
Aug 16 at 14:28
@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.
– user160919
Aug 16 at 15:05
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04
 |Â
show 1 more comment
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $q$ be a prime power and $omega=exp(2pi i/q)$. For a fixed $yinmathbbZ_q^n$, the map
$$mathbbZ_q^nni xmapsto omega^xcdot y=omega^x_1y_1+dots+x_ny_n$$
is a character of $mathbbZ_q^n$. The Hamming weight $operatornamewt_H$ of $xinmathbbZ_q^n$ is the number of nonzero entries in $x$. Let
$X_i=xin mathbbZ_q^nmid operatornamewt_H(x)=i.$ I want to prove that the sum
$sum_xin X_iomega^xcdot y$ is constant for all $yin 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,yin X_k$ there exists $gin S_n$ such that $gx=y$. Thus, we have
$$sum_xin X_iomega^xcdot gy=sum_xin X_iomega^g^-1xcdot y=sum_xin X_iomega^xcdot y.$$
But I don't see that the sum is constant if $qgeq 3$.
EDIT: I think that for $qgeq 3$ we could use a similar argument. If we take the group $S_q-1^nwr S_n$, which operates on $xinmathbbZ_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 $yin X_k$. But I'm not completely sure that this is the right argument.
abstract-algebra combinatorics finite-fields coding-theory algebraic-combinatorics
asked Aug 16 at 8:38
user160919
19411
Let $q$ be a prime power and $omega=exp(2pi i/q)$. For a fixed $yinmathbbZ_q^n$, the map
$$mathbbZ_q^nni xmapsto omega^xcdot y=omega^x_1y_1+dots+x_ny_n$$
is a character of $mathbbZ_q^n$. The Hamming weight $operatornamewt_H$ of $xinmathbbZ_q^n$ is the number of nonzero entries in $x$. Let
$X_i=xin mathbbZ_q^nmid operatornamewt_H(x)=i.$ I want to prove that the sum
$sum_xin X_iomega^xcdot y$ is constant for all $yin 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,yin X_k$ there exists $gin S_n$ such that $gx=y$. Thus, we have
$$sum_xin X_iomega^xcdot gy=sum_xin X_iomega^g^-1xcdot y=sum_xin X_iomega^xcdot y.$$
But I don't see that the sum is constant if $qgeq 3$.
EDIT: I think that for $qgeq 3$ we could use a similar argument. If we take the group $S_q-1^nwr S_n$, which operates on $xinmathbbZ_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 $yin X_k$. But I'm not completely sure that this is the right argument.
abstract-algebra combinatorics finite-fields coding-theory algebraic-combinatorics
asked Aug 16 at 8:38
user160919
19411
edited Aug 16 at 15:14
asked Aug 16 at 8:38
user160919
19411
asked Aug 16 at 8:38
user160919
19411
asked Aug 16 at 8:38
user160919
19411
19411
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
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.
– Jyrki Lahtonen
Aug 16 at 14:28
@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.
– user160919
Aug 16 at 15:05
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04
 |Â
show 1 more comment
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
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.
– Jyrki Lahtonen
Aug 16 at 14:28
@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.
– user160919
Aug 16 at 15:05
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
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.
– Jyrki Lahtonen
Aug 16 at 14:28
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.
– Jyrki Lahtonen
Aug 16 at 14:28
@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.
– user160919
Aug 16 at 15:05
@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.
– user160919
Aug 16 at 15:05
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04
 |Â
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2884550%2fconstant-sum-of-characters%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I think that the constancy eventually follows from the fact that $$sum_xin BbbZ_q, xneq0omega^xy=-1$$ whenever $yneq0$ 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.
– Jyrki Lahtonen
Aug 16 at 14:23
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.
– Jyrki Lahtonen
Aug 16 at 14:28
@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.
– user160919
Aug 16 at 15:05
@JyrkiLahtonen: I see how to prove that this sum is constant by using $$sum_xin BbbZ_q, xneq0omega^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.
– user160919
Aug 16 at 15:23
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-1wr S_n$ will do). When $q$ is not a prime, equivalently, when $BbbZ_q$ is not a field, I think there is problem. I don't think that we have equality of the multisets $xcdot y$ and $xcdot 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$.
– Jyrki Lahtonen
Aug 17 at 10:04