View topic - 2n+1 elements from F_3^n. • Art of Problem Solving

2n+1 elements from F_3^n.

Page 1 of 1

[ 14 posts ]

Author

Message

lzw75

Posts: 16

Posted: Mar 13, 2008, 7:46 am • # 1

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.

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 13, 2008, 3:30 pm • # 2

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

Last edited by darij grinberg on Nov 18, 2008, 5:52 am, edited 1 time in total.

lzw75

Posts: 16

Posted: Mar 13, 2008, 7:16 pm • # 3

darij grinberg wrote:

Wow, thank you so much! :lol:

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?

lzw75

Posts: 16

Posted: Mar 14, 2008, 8:44 am • # 4

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.

Fedor Petrov

Posts: 471
Location: Saint-Petersburg

Posted: Mar 14, 2008, 9:20 am • # 5

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.

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 14, 2008, 9:43 am • # 6

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

Fedor Petrov Posts: 471 Location: Saint-Petersburg	Posted: Mar 14, 2008, 9:50 am • # 7 Of course, it is a typo, thank you. I do not remember the settings of all these theorems, since they follow from CN.

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 14, 2008, 10:00 am • # 8

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 14, 2008, 11:46 am • # 9

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}\righ...$ ,
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}\righ...$
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$ .
(Hereby, $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}\righ...$
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}\righ...$ .

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

lzw75

Posts: 16

Posted: Mar 15, 2008, 7:23 am • # 10

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

darij grinberg wrote:

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=43766]
@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.

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 20, 2008, 9:58 am • # 11

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.artofproblemsolving.com/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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

mdevos

Posts: 2

Posted: Mar 23, 2008, 4:56 pm • # 12

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

darij grinberg

Posts: 5937
Location: Karlsruhe / Munich

Posted: Mar 23, 2008, 5:05 pm • # 13

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

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

mdevos Posts: 2	Posted: Nov 27, 2008, 12:43 pm • # 14 I was writing without thinking.. you are completely correct.

Display posts from previous: Sort by

Share on Facebook

Previous topic | Next topic

Community » Olympiad Section » Combinatorics » Combinatorics Open Questions

All times are UTC - 8 hours [ DST ]

Moderators: MithsApprentice, N.T.TUAN, Peter, darij grinberg, orl, pbornsztein, freemind, Megus, High School Olympiad Moderators

Page 1 of 1

[ 14 posts ]

Login

Username: Password: Log me on automatically each visit

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Learn LaTeX

Make your mathematical writing look like a pro's. Visit the AoPS LaTeX tutorial and soon you'll be producing top-quality mathematical output.

Introduction to Number Theory

Primes, factoring, divisors, base numbers, and more. Over 500 problems! Great for MATHCOUNTS and AMC preparation.