Ένα σύνολο $A$ αριθμών (ακεραίων, πραγματικών ή μελών μιας οποιασδήποτε προσθετικής ομάδας, όπως π.χ. η ομάδα $\mathbb{Z}_m$ των υπολοίπων mod $m$ με πράξη την πρόσθεση mod $m$) λέγεται sum-free αν
για κάθε $x, y, z \in A$ ισχύει $x+y \neq z$
Για παράδειγμα, το σύνολο όλων των περιττών ακεραίων αριθμών είναι sum-free όπως είναι και το σύνολο ${n, n+1, n+2, \ldots, 2n-1}, όπως εύκολα μπορεί κανείς να επιβεβαιώσει.
Σήμερα δώσαμε μια πιθανοθεωρητική απόδειξη του παρακάτω θεωρήματος:
Αν $A$ είναι ένα σύνολο $N$ θετικών ακεραίων τότε υπάρχει sum-free υποσύνολο $E \subseteq A$ με $|E| > N/3$.
Ας είναι $n_1 < n_2 < \cdots < n_N$ τα στοιχεία του $A$ και ας είναι $p>n_N$ ένας πρώτος αριθμός της μορφής $3k+2$ (υπάρχουν άπειροι τέτοιοι πρώτοι αριθμοί σύμφωνα με το θεώρημα του Dirichlet για πρώτους σε αριθμητικές προόδους).
Δείξαμε πρώτα ότι το σύνολο $M = \{k+1, \ldots, 2k+1\}$ είναι sum-free mod $p$ (αυτό σημαίνει ότι για κάθε $x, y, z \in M$ ισχύει $x+y \neq z \bmod p$).
Ας είναι $t \in \{1, 2, \ldots, p-1\}$ τυχαίο (με ομοιόμορφη κατανομή). Αφού το σύνολο $tA \cap M$ (εδώ $tA = \{ta: a \in A\}$) είναι υποσύνολο του $M$ έπεται ότι είναι και αυτό sum-free mod $p$ και άρα είναι και sum-free ως σύνολο ακεραίων.
Αφού κάθε τέτοιο $t$ είναι αντιστρέψιμο $\bmod p$ (με άλλα λόγια ο δακτύλιος $\mathbb{Z}_p = \{0, 1, \ldots, p-1\}$ είναι και σώμα) έπεται ότι το σύνολο
$A \cap t^{-1} M = t^{-1}(tA \cap M)$
είναι και αυτό sum-free. (Εδώ $t^{-1}$ είναι το πολλαπλασιαστικό αντίστροφο του $t \bmod p$.)
Έπειτα δείξαμε ότι $\mathbb{E}(|A \cap t^{-1}M|) > N/3$, το οποίο σημαίνει ότι υπάρχει ένα $t$ για το οποίο το υποσύνολο $E = A \cap t^{-1}M$ του $A$ είναι sum-free και μεγέθους $>N/3$ όπως έπρεπε να δείξουμε.
Μπορείτε να δείτε τις λεπτομέρειες της απόδειξης στο Θεώρημα 1.2 εδώ.
Παρακάτω υλοποιούμε την απόδεξη αυτή ως έναν πιθανοθεωρητικό αλγόριθμο. Προσέξτε ότι το αποτέλεσμα δεν είναι εγγυημένα μεγέθους $>N/3$, αλλά ότι κάποιες φορές από αυτές που τρέχει ο αλγόριθμος το αποτέλεσμα θα είναι $>N/3$.
import numpy as np
p = 113 # Ο πρώτος αριθμός της απόδειξης
k = 37 # p = 3k+2
A = [ 5, 6, 7, 8, 20, 21, 22, 23, 50, 55, 60, 65, 70, 71, 72, 80, 81, 82, 83, 84, 85]
# Το A είναι το σύνολο από το οποίο εξάγουμε το μεγάλο sum-free σύνολο
N = len(A) # το μέγεθος του A
t = np.random.randint(1, p) # τυχαίο στοιχείο του 1, 2, ..., p-1
E = [] # αυτό θα είναι το υποσύνολο του A που φτιάχνουμε. είναι εγγυημένα sum-free αλλά δεν υπάρχει εγγύηση για το μέγεθός του
for a in A:
x = t*a % p # κρατάμε κάποιο στοιχείο a του A αν ta πέφτει μέσα στο M={k+1,...,2k+1}
if k+1 <= x <= 2*k+1:
E.append(a)
print(A)
print(E)
print(f"E έχει μέγεθος {len(E)}")
print(f"A έχει μέγεθος {len(A)}")