Combinatorial Nullstellensatz

#1

Με αφορμή ένα post του Αναστάση εδώ.

Γνωρίζουμε ότι ένα πολυώνυμο βαθμού

δεν μπορεί να έχει περισσότερες από

ρίζες. Πώς γενικέυεται αυτό σε πολυώνυμα πολλών μεταβλητών; Ο Noga Alon έχει δώσει την εξής απάντηση

Θεώρημα (Combinatorial Nullstellensatz): Έστω

ένα σώμα και

ένα πολυώνυμο στο $F[x_1,\ldots,x_n]$ . Έστω ότι το

έχει βαθμό

και ο συντελεστής του όρου $x_1^{m_1} \cdots x_n^{m_n}$ όπου $m_1 + \cdots + m_n$ , όπου $m_1 + \cdots + m_n$ είναι μη μηδενικός. Αν $S_1,\ldots,S_n$ υποσύνολα του

με $|S_i| \geqslant m_1 + 1$ για κάθε

τότε υπάρχει $s_1 \in S_1,\ldots,s_n \in S_n$ ώστε $f(s_1,\ldots,s_n) \neq 0$ .

Το θεώρημα αυτό έχει βρει αρκετές εφαρμογές σε αριθμοθεωρία και συνδυαστική. Δίνω σαν άσκηση μια εφαρμογή

Θεώρημα Cauchy-Davenport: Έστω

πρώτος και A,B

μη κενά υποσύνολα του $\mathbb{Z}_p$ . Τότε $|A+B| \geqslant \min\{p,|A|+|B|-1\}$ .

Εδώ, $A+B = \{a+b:a \in A,b \in B\}$ .

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#2

Μιας και έμεινε αρκετό καιρό, βάζω μια απάντηση:

Μπορούμε να υποθέσουμε ότι $|A|+|B| \leqslant p$ . Αν όχι τότε για κάθε $x \in \mathbb{Z}_p$ τα σύνολα

και $x-B = \{x-b:b \in B\}$ έχουν μη κενή τομή (περιστεροφωλιά) και άρα υπάρχουν $a\in A,b \in B$ με a+b=x

. Άρα $|A+B| = |\mathbb{Z}_p| = p$ .

Μπορούμε επίσης να υποθέσουμε ότι $|A+B| \leqslant |A|+|B|-2 \leqslant p-2$ . Παίρνουμε $C \supseteq A+B$ με |C| = |A|+|B|-2 = (|A|-1) + (|B|-1)

. Ο συντελεστής του $x^{|A|-1}y^{|B|-1}$ στο πολυώνυμο $f(x,y) = \prod_{c \in C}(x+y-c)$ ισούται με $\binom{|C|}{|A|-1} \neq 0 \bmod p$ . Παίρνοντας S_1 = A,m_1=|S_1|-1=|A|-1,S_2=B,m_2=|B|-1

στο θεώρημα βρίσκουμε ότι υπάρχει $a \in A,b \in B$ ώστε $f(a,b) \neq 0$ , άτοπο.

#3

Θεώρημα Erdos-Ginzburg-Ziv: Έστω $a_1,a_2,\ldots,a_{2n-1} \in \mathbb{Z}_n$ .Να δειχθεί ότι υπάρχουν $1 \leqslant i_1 < i_2 < \cdots < i_n \leqslant 2n-1$ ώστε $a_{i_1} + \cdots + a_{i_n} = 0 \bmod n$ .

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Combinatorial Nullstellensatz

Combinatorial Nullstellensatz

Re: Combinatorial Nullstellensatz

Re: Combinatorial Nullstellensatz

Μέλη σε σύνδεση