2n+1 elements from F_3^n.

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

12 users

TOPICS

No tags match your search

M

No tags match your search

M

2n+1 elements from F_3^n.

G H J

Reveal topic tags

pigeonhole principle

abstract algebra

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

lzw75

#1 h Mar 13, 2008, 2:46 PM • 2 Y

Y by Adventure10, Mango247

Hi.

First consider the following trivial problem:

- given any x_1, ... , x_{n+1} from F_2^n (F_2 = integers mod 2), not necessarily distinct, we can find a non-empty subset of them which sums up to 0.

This can be easily solved by either pigeonhole principle or linear algebra over F_2. What about the following?

- given any x_1, ... , x_{2n+1} from F_3^n (F_3 = integers mod 3), not necessarily distinct, we can find a non-empty subset of them which sums up to 0.

Is it true? Thanks - it doesn't look too hard, but I can't seem to solve it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#2 h Mar 13, 2008, 10:30 PM • 2 Y

Y by Adventure10, Mango247

Beautiful!!!!!!!!! More generally:

Theorem 1. If $p$ is a prime, $n$ is an integer, and $x_1$ , $x_2$ , ..., $x_{\left(p - 1\right)n + 1}$ are $\left(p - 1\right)n + 1$ elements of the vector space $\mathbb{F}_p^n$ , then there exists a non-empty subset $T\subseteq\left\{1,2,...,\left(p - 1\right)n + 1\right\}$ such that $\sum_{t\in T}x_t = 0$ .

I have just put a proof of this on my website: See problem 2 in the note St. Petersburg 2003: An alternating sum of zero-sum subset numbers.

darij

This post has been edited 1 time. Last edited by darij grinberg, Nov 18, 2008, 12:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

lzw75

#3 h Mar 14, 2008, 2:16 AM • 2 Y

Y by Adventure10, Mango247

darij grinberg wrote:

Beautiful!!!!!!!!! More generally:

Theorem 1. If $p$ is a prime, $n$ is an integer, and $x_1$ , $x_2$ , ..., $x_{\left(p - 1\right)n + 1}$ are $\left(p - 1\right)n + 1$ elements of the vector space $\mathbb{F}_p^n$ , then there exists a non-empty subset $T\subseteq\left\{1,2,...,\left(p - 1\right)n + 1\right\}$ such that $\sum_{t\in T}x_t = 0$ .

I have just put a proof of this on my website: See problem 2 in the note St. Petersburg 2003: An alternating sum of zero-sum subset numbers.

darij

Wow, thank you so much!

This problem has been bugging me for quite a while, and I didn't realise it's so involved.

But now another thing bugs me: why does p have to be prime? If we modify the problem to (p-1)n+1 elements from (Z/pZ)^n, where p is not necessarily prime, does it not hold anymore?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

lzw75

#4 h Mar 14, 2008, 3:44 PM • 2 Y

Y by Adventure10, Mango247

Or, another interesting spin-off would be: is there an efficient algorithm to find such a subset?

[ Note : efficient = having runtime which is polynomial in n. ]

Clearly, when p=2 one can just use Gaussian elimination. What about higher p?

It turns out this question solves a very interesting problem I came across some time ago. Will post it and my thoughts later.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

520 posts

#5 h Mar 14, 2008, 4:20 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

It's just another form of a known theorem.

Denote our $N>(p-1)m$ vectors $x_i=(a_1^i,a_2^i,\dots,a_m^i)$ , $i$ varies from 1 to $N$ . Then we need to find $\epsilon_i\in\{0,1\}$ such that $m$ linear forms $l_k(\epsilon_1,\epsilon_2,\dots,\epsilon_N): =\sum_{i=1}^N a_i^k\epsilon_i=0$ vanish for $k=1$ , $2$ , $\dots$ , $m$ . Also, not all $\epsilon$ 's must vanish.

It is a standard application of Combinatorial Nullstellensatz, maybe it is called Chevalley-Waring theorem.

Indeed, consider the polynomial $F(\epsilon_1,\epsilon_2,\dots,\epsilon_N)=(1-\epsilon_1)(1-\epsilon_2)\dots(1-\epsilon_N)-\prod_{k=1}^m (1-l_k^{p-1})$

It's coefficient in $\epsilon_1\epsilon_2\dots \epsilon_m$ does not vanish and this term is of maximal degree, hence there exists by CN some $\epsilon_i\in\{0,1\}$ such that $F$ does not vanish. Since all $\epsilon$ 's equal to 0 do not satisfy, some $\epsilon$ equals to 1, hence first summand vanish, hence the second does not, hence all $l_k$ vanish, as we desire.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#6 h Mar 14, 2008, 4:43 PM • 1 Y

Y by Adventure10

Thanks, this is nice! No, the Combinatorial Nullstellensatz is not the same as Chevalley-Warning; actually, I have tried Chevalley-Warning, but it did not work. I should have tried the Combinatorial Nullstellensatz instead.

A little typo correction:

Fedor Petrov wrote:

It's coefficient in $\epsilon_1\epsilon_2\dots \epsilon_m$

This should be "Its coefficient before $\epsilon_1\epsilon_2\dots\epsilon_N$ ".

I am thinking about the case of non-prime $p$ . Lemma 3 in my note was formulated for rings and not just for fields $\mathbb{F}_p$ , but I am missing something like Lemma 0 for $\mathbb{Z}\slash n\mathbb{Z}$ - a polynomial that is $1\mod n$ if $n\mid x$ and $0\mod n$ otherwise. Well, such a polynomial (with integer coefficients) doesn't exist for any non-prime $n$ , but maybe something similar can be found.

I'll keep you informed.

darij

This post has been edited 1 time. Last edited by darij grinberg, Mar 14, 2008, 4:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

520 posts

#7 h Mar 14, 2008, 4:50 PM • 3 Y

Y by Adventure10, Mango247, Mango247

Of course, it is a typo, thank you.

I do not remember the settings of all these theorems, since they follow from CN.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#8 h Mar 14, 2008, 5:00 PM • 2 Y

Y by Adventure10, Mango247

The Chevalley-Warning theorem in its strong form ("the number of solutions is divisible by $p$ ") does not really follow from the CN. Also, there are some stronger versions of the CN floating around, and if I am not mistaken, some stronger versions of CW as well. It's not harmful to know more of these.

Anyway, did anyone try some combinatorial approaches? These could be useful for the case of non-prime $p$ .

@Lzw75: are you trying to find some paths in graphs? I'm just wondering...

darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#9 h Mar 14, 2008, 6:46 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Progress!

Problem 2 Extension #1. Let $s$ be a prime power. Let $m$ be an integer, and let $n > \left( s - 1\right) m$ be an integer. Let $a_{1}$ , $a_{2}$ , ..., $a_{n}$ be $n$ elements of the $\mathbb{Z}\slash s\mathbb{Z}$ -module $\left(\mathbb{Z}\slash s\mathbb{Z}\right)^{m}$ . Prove that there exists a non-empty subset $T\subseteq\left\{ 1,2,...,n\right\}$ such that $\sum\limits_{t\in T}a_{t} = 0$ .

What is happening here?

Actually I have tried to generalize my approach. We can consider $a_{1}$ , $a_{2}$ , ..., $a_{n}$ as elements of $\mathbb{Z}^m$ rather than as elements of $\left(\mathbb{Z}\slash s\mathbb{Z}\right)^{m}$ , and then we want to show that there exists a non-empty subset $T\subseteq\left\{ 1,2,...,n\right\}$ such that $\sum\limits_{t\in T}a_{t}$ is a vector with all components divisible by $s$ .

As an analogue of the equation (6) in my note, we have the identity
$\sum_{T\subseteq\left\{1,2,...,n\right\}} \left( - 1\right)^{\left|T\right|} \prod_{j = 1}^m P\left(\sum_{t\in T}a_{t,j}\right) = 0$ ,
for any polynomial $P\in\mathbb{Q}\left[X\right]$ of degree $\leq s - 1$ . (This follows from Lemma 3 since $\prod_{j = 1}^m P\left(\sum_{t\in T}a_{t,j}X_t\right)$ is a polynomial of $X_1$ , $X_2$ , ..., $X_n$ of degree $\leq m\left(s - 1\right) < n$ . Don't forget that $a_{t,j}$ are integers here (rather than residues as in the note), and the identity above is an identity about integers.)

The reason why I had chosen the polynomial $P\left(X\right) = 1 - X^{s - 1}$ in my note is its following property: $P\left(x\right)$ is divisible by $s$ if $x$ is not divisible by $s$ , and $\equiv 1\mod s$ if $x$ is divisible by $s$ . (This is basically Lemma 0 of the note.) If we assume that there is no non-empty set $T\subseteq\left\{ 1,2,...,n\right\}$ such that $\sum\limits_{t\in T}a_{t}$ is a vector with all components divisible by $s$ , then the sum
$\sum_{T\subseteq\left\{1,2,...,n\right\}} \left( - 1\right)^{\left|T\right|} \prod_{j = 1}^m P\left(\sum_{t\in T}a_{t,j}\right)$
would thus consist of a lot of terms divisible by $s$ and exactly one term not divisible by $s$ (namely, the term corresponding to $T = \emptyset$ ), and hence it would be not divisible by $s$ , contradicting to it being $= 0$ .

How can this be generalized to $s$ being a prime power, say $s = p^{\alpha}$ for $p$ prime? All we need is a polynomial $P\in\mathbb{Z}\left[X\right]$ of degree $\leq s - 1$ such that there exists an integer $\beta$ such that

$p^{\beta + 1}\mid P\left(x\right)$ for integers $x$ such that $p^{\alpha}\nmid x$ ;
$p^{\beta}\parallel P\left(x\right)$ for integers $x$ such that $p^{\alpha}\mid x$ .
(Here, $p^{\beta}\parallel u$ is just an abbreviation for $p^{\beta}\mid u$ and $p^{\beta + 1}\nmid u$ ; in words: $p^{\beta}$ is the highest power of $p$ that divides $u$ .)

If we have such a polynomial $P$ , then we can argue as follows: Assume that there is no non-empty set $T\subseteq\left\{ 1,2,...,n\right\}$ such that $\sum\limits_{t\in T}a_{t}$ is a vector with all components divisible by $s$ . Then, the sum
$\sum_{T\subseteq\left\{1,2,...,n\right\}} \left( - 1\right)^{\left|T\right|} \prod_{j = 1}^m P\left(\sum_{t\in T}a_{t,j}\right)$
consists of a lot of terms divisible by $p^{m\beta + 1}$ (namely, all terms corresponding to non-empty subsets $T\subseteq\left\{ 1,2,...,n\right\}$ ) and exactly one term not divisible by $p^{m\beta + 1}$ (namely, the term corresponding to $T = \emptyset$ ; the highest power of $p$ that divides it is $p^{m\beta}$ ), so that this sum cannot be $0$ , contradicting

$\sum_{T\subseteq\left\{1,2,...,n\right\}} \left( - 1\right)^{\left|T\right|} \prod_{j = 1}^m P\left(\sum_{t\in T}a_{t,j}\right) = 0$ .

A polynomial $P$ satisfying our needs is the following one:

$P\left(X\right) = \binom{X - 1}{p^{\alpha} - 1}$

(remember, $p^{\alpha} = s$ ). I leave it to the reader to show that this polynomial does what we want from it (hint: $\beta=0$ ; use that $\binom{X - 1}{p^{\alpha} - 1} = \frac {p^{\alpha}}{X}\cdot\binom{X}{p^{\alpha}}$ ).

Now the question is whether we can find similar polynomials $P$ for generic (non-prime-power) $s$ , or whether we should try finding counterexamples instead.

darij

This post has been edited 1 time. Last edited by darij grinberg, Jul 3, 2021, 6:26 PM
Reason: Hereby -> Here

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

lzw75

#10 h Mar 15, 2008, 2:23 PM • 2 Y

Y by Adventure10, Mango247

Thanks for the two beautiful proofs. I'm particularly impressed with the use of the Combinatorial Nullstellensatz.

darij grinberg wrote:

@Lzw75: are you trying to find some paths in graphs? I'm just wondering...

darij

The problem I had in mind was as follows (source forgotten: it's somewhere on the Net) :

- Find a positive perfect cube $x > 1$ , such that $\sigma(x)$ , the sum of the positive divisors of $x$ , is also a perfect cube.

The approach I had in mind is as follows:

(i) Prepare two lists of small primes $S$ and $T$ , where $S = \{2,3,5,... \}$ has $2n + 1$ elements and $T = \{2,3,5,.... \}$ has $n$ elements. They can be any sets of primes, although it's advantageous to pick smaller ones.
(ii) For each prime $p \in S$ , find an appropriate power $p^{3r}$ , such that $\sigma(p^{3r})$ can be written as a product of primes in $T$ .
(iii) Each $\sigma(p^{3r})$ can then be written as a product of a cube, and prime powers $q_i^{a_i}$ , where each $q_i \in T$ and each $a_i = 0, 1, 2$ . Thus we obtain $2n + 1$ vectors of the form $(a_1, \dots, a_n) \in F_3$ . An algorithmic solution to the problem I posed would help us find a solution to this problem.

Note: I might be using a sledgehammer to kill a fly here, but this method was inspired from the method of quadratic sieve used in prime factoring.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#11 h Mar 20, 2008, 4:58 PM • 2 Y

Y by Adventure10, Mango247

Unfortunately, I have no experience with prime factoring algorithms, but I wouldn't compare prime factoring with a fly...

Anyway I am posting here again in order to say that what I proved above (the case of $s$ being a prime power) was already shown in
http://www.mathlinks.ro/viewtopic.php?t=6015 :

vess wrote:

Our problem is an easy corollary. We will show, more generally (the problem is a special case with $k = p - 1$ ) that if we are given more than $k(p - 1)$ vectors in $\mathbb{F}_p^k$ , then some of them have sum $0$ . Let $s = 1 + k(p - 1)$ , and let $v_i = (a_{i1},\ldots,a_{ik})$ , $1 \leq i \leq s$ , be the given vectors. Consider the $k$ polynomials on $s$ variables
$f_j(x_1,\ldots,x_s) : = \sum_i a_{ij} x_i^{p - 1}.$
These polynomials fulfil the hypothesis of the Chevalley-Warning Theorem, for the sum of their degrees is $k(p - 1)$ , which is less than the number $s = 1 + k(p - 1)$ of variables. Note that the system $f_1 = \cdots = f_k = 0$ has the trivial solution $x_1 = \cdots = x_s = 0$ . By the Chevalley-Warning theorem, it has another one, say $(\alpha_1,\ldots,\alpha_s)$ . Now, set $I : = \{i \, | \, \alpha_i \neq 0\}$ . This set is non-empty and, by Fermat's Little Theorem, we have
$\sum_{i \in I} v_i = (0,\ldots,0),$
as desired. The proof is complete.

I don't see yet what this all implies for $s$ not being a prime power, but the topic is one single treasury.

EDIT:

1. Olson's theorem (see the topic linked above) is a generalization of the case of $s$ being a prime power. I will check whether my proof generalizes to a proof of Olson's theorem.

2. Another theorem by Olson states that if $a$ and $b$ are positive integers satisfying $a\mid b$ , then from $a + b - 1$ vectors in $\left(\mathbb{Z}\slash \left(a\mathbb{Z}\right)\right)\times\left(\mathbb{Z}\slash\left(b\mathbb{Z}\right)\right)$ , we can always choose a non-empty subset with zero sum, at least according to this link. Another link states the same but forgetting the (important!) condition $a\mid b$ .

3. The case of $s$ being not a prime power seems to be an open problem.

darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

mdevos

#12 h Mar 23, 2008, 11:56 PM • 2 Y

Y by Adventure10, Mango247

I was delighted to discover this website, and to see such nice discoveries taking place here.

One small correction though: in Grinberg's previous post, specifically Edit #2, the following theorem of Olson is referred to: Every sequence of $a+b-1$ elements from the group ${\mathbb Z}_a \times {\mathbb Z}_b$ has a nontrivial subsequence which sums to zero (here ${\mathbb Z}_a = {\mathbb Z}/a{\mathbb Z}$ ). I mention this theorem here. It is suggested that the condition $a|b$ is needed for this theorem, but it is not.. indeed it's an easy consequence of the basic structure theorem for abelian groups that for every pair of positive integers $a,b$ , there exist $m,n$ so that $m|n$ and ${\mathbb Z}_a \times {\mathbb Z}_b \cong {\mathbb Z}_m \times {\mathbb Z}_n$ .

Cheers,
Matt

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#13 h Mar 24, 2008, 12:05 AM • 2 Y

Y by Adventure10, Mango247

Hello Matt,

mdevos wrote:

One small correction though: in Grinberg's previous post, specifically Edit #2, the following theorem of Olson is referred to: Every sequence of $a + b - 1$ elements from the group ${\mathbb Z}_a \times {\mathbb Z}_b$ has a nontrivial subsequence which sums to zero (here ${\mathbb Z}_a = {\mathbb Z}/a{\mathbb Z}$ ). I mention this theorem here. It is suggested that the condition $a|b$ is needed for this theorem, but it is not.. indeed it's an easy consequence of the basic structure theorem for abelian groups that for every pair of positive integers $a,b$ , there exist $m,n$ so that $m|n$ and ${\mathbb Z}_a \times {\mathbb Z}_b \cong {\mathbb Z}_m \times {\mathbb Z}_n$ .

I think there was a slight misunderstanding here. Of course, every group of the form ${\mathbb Z}_a \times {\mathbb Z}_b$ can be rewritten as ${\mathbb Z}_m \times {\mathbb Z}_n$ with $m\mid n$ , but your formulation can be understood as if we don't need to rewrite it in this form. But this is wrong: $m + n - 1$ is, in general, distinct from $a + b - 1$ . For instance, the group $\mathbb{Z}_2\times\mathbb{Z}_3$ has Davenport constant $6$ , although $2 + 3 - 1 = 4\neq 6$ . That's what I was referring to. I hope it becomes clearer now (it's past midnight here and my skills at explaining are not too great).

darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

mdevos

#14 h Nov 27, 2008, 7:43 PM • 2 Y

Y by Adventure10 and 1 other user

I was writing without thinking.. you are completely correct.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a