Προσθετική θεωρία αριθμών

[Ilias_Zad]

Πρόκειται για πολύ καλό αποτέλεσμα. Θα ήταν ωραίο να δούμε διάφορες αποδείξεις:
Έστω . Aν είναι μια ακολουθία ακεραίων τότε υπάρχει μια υπακολουθία της: ώστε το άθροισμα των όρων της να διαιρείται από .

[emouroukos]

Πρόκειται για το περίφημο θεώρημα Erdős-Ginzburg-Ziv (1961). Στο άρθρο των Alon-Dubiner, που βρίσκεται εδώ, παρατίθενται πέντε αποδείξεις!

[Demetres]

Μια έκτη απόδειξη είναι με το Combinatorial Nullstellensatz. (Η πέμπτη απόδειξη στο άρθρο των Alon και Dubiner είναι ένας "πρόδρομος" του Combinatorial Nullstellensatz που ανέπτυξε αργότερα ο Alon.)

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

[Ilias_Zad]

Ωραίο το link. Κάλυψε όλες τις αποδείξεις που γνώριζα με το παραπάνω

ΥΓ. Δημήτρη στο άλλο θέμα έχεις λύση απευθείας από το Nullstellensatz χωρίς να περάσεις ενδιάμεσα από το Cauchy-Davenport;

[Demetres]

Ηλία, και τα τρία Cauchy-Davenport/Chevalley-Warning/permanent lemma αποδεικνύονται με Nullstellensatz αλλά δεν θα έλεγα τις αποδείξεις του Erdos-Ginzburg-Ziv μέσω αυτών «διαφορετικές».

Η απόδειξη όμως μέσω του permanent lemma χρησιμοποιεί ένα πολύ ειδικό πίνακα και σε αυτήν την περίπτωση το Nullstellensatz μπορεί να χρησιμοποιηθεί πιο άμεσα χωρίς να αποδείξει γενικά το permanent lemma. Αυτήν την απόδειξη θα την χαρακτήριζα διαφορετική.