Phương pháp chủ yếu để áp dụng biến đổi Fourier vào lý thuyết các tập hợp tổng hoặc các cấp cộng là dựa vào khái niệm độ lệch Fourier của tập hợp đó (còn gọi là độ lệch tuyến tính hoặc tính giả ngẫu nhiên). Nói một cách sơ lược, khái niệm này chia các tập hợp theo hai thái cực: các tập khá chính quy (có dáng điệu như các tập ngẫu nhiên, đặc biệt là các tập tổng lặp) và các tập không thật chính quy (có dáng điệu như các cấp số).
Định nghĩa 2.1.1. [Độ lệch Fourier| Cho Z là một nhóm cộng hữu hạn. Nếu 4A là một tập con của Z, thì ta định nghĩa độ lệch Fourier
|| Al ctia A là số:
I4ll,:= sup [ẽa(6). €cZ\{0}
Đại lượng này không âm, ||A||„ = 0 nếu và chỉ nếu A = Z hoặc
A =Ũ. Nó tuân theo luật đối xứng
I4, = |] — Allu = |A + Ally = 112 \ Alla, VA € Z.
Chú ý rằng || - || là không đơn điệu, tức là 4 C không suy ra được ||A||, < ||P|l. Tuy nhiên, độ lệch Fourier tuân theo bất đẳng thức tam giác. Độ lệch Fourier ||A||„ có thể lớn bằng mật độ Pz(1), nhưng thường là nhỏ. Các tap A có độ lệch Fourier nhỏ hơn œ, thường được gọi là tập œ- đều hoặc tập a- giả ngẫu nhiên; các tập với độ lệch Fourier nhỏ được gọi là đều tuyến tính, đều Gowers cấp 1, hoặc giả ngẫu nhiên.
Múi liên quan giữa độ lệch Fourier và các tập tổng được mô tả trong
2 ^
bồ đề sau.
Bổ đề 2.1.2. [Tính đều suy ra các tập tổng lớn]
Chon > 3, và Ai, 4;,..., A„ là các tập hợp cộng tính trong nhóm cộng hữu hạn Z.
Khi đó với Vz € Z, (œị,d¿,...,d„) € Ái x... < AÁ„ ta có 1
a S |[Aaflu s+ An—2lluPz(An-1)?P2(An)?.
|{(a1,a2,..-,@n) :ư =úp +... + a„}|—Pz(Ai) —...— Pz(A„)
Đặc biệt, nếu ta có
\| Ay Ì. sae | An—allu < Pz(4j) .... Pz(An—-2)Pz(An-1)?Pz(An) Nie
Tat nhiên, một kết quả tương tự là đúng nếu ta hoán đổi thứ tự Ai,..., A„. Chú ý rằng đại lượng Pz(44)...Pz(4„) là giá trị mong đợi của
Ppt las 2st) € Ar XX Anta = a +. + On}1
nếu các sự kiện a; € Aj,...,a, € 4„ là độc lập từng đôi với điều kiện # = ai +... +ứ„. Điều này giải thớch tại sao tớnh đều cũn được gọi là tính giả ngẫu nhiên.
Chứng mình.
Theo (1.13), ham 14, *...* 14, c6 bién doi Fourier Ta, ` .TA,.
Áp dụng công thức Fourier ngược (1.7), (1.10), Bất đẳng thức Cauchy- Schwarz va (1.11) ta cé:
14, *...* 14, (2) 1
= Re la, *...*% la,(z)
= Re So 14, (8) sở - Ta,(€)c(œ -€) ccZ
>1a,(0)...1a,(0)— ` [i¿,(©l...[Ta,(6)|
€eZ\{0}
> Pz(A1)...Pz(An) = Arle --JAn—2llu 95 (Pa, (©) La, (6)
ccZ
> Pz(4¡)...Pz(4A¿) — |lAillu--- An—allullta,.. (Ollewllta, (Elle
= P;(A,)...Pz(An) — ||Aillu--- || An—2lluPz(An-1)?Pz(An)?-
Tương tự ta có
la, *x...*% 14, (x) < Pz(4j) ...Pz(A,)
+ | Aa lla ... | An—2|luPz(An-1)?Pz(An) . NIK
Theo định nghĩa của tích chập
lạ *...% 14 (x) 1
= |ZI! *|{(ai, as,...., Qn) € A, x XA, @ =a, +...+a,}|
và do đó bổ đề được chứng minh.
Bổ đề 2.1.3. [Đánh giá tổng Gauss] Cho F' là trường hữu hạn với cấp lễ và A = F^? = {a?:ac€ F} là tập các bình phương của các phan tit trong F. Khi đó:
1 1
|All uSaat 2|F | 2|F |p T°
Chứng mình. Lấy € € F \ {0}. Do mọi phần tử khác 0 trong A déu có đúng hai cách biểu diễn dưới dạng a”, nên ta có:
a 1 1 1
lẠ(€) = Ty È €(—Ê*#) = st ay DL e(-€-@”). rm oF * FL
Mặt khác, ta có:
do e(-€ 0") mmằ... “` (a? 0%) 2
ack ack a,beF
= YF e(g-(a? = (a+ h)’))
_ ằ e(—Ê - h°) ằ c(€ - 2ah).
heF ack
Néu h £0 thi 2h 40 va
S ` e(£ - 2ah) = À `c(£ -c) =0
acF ceF
nhờ vào Bo dé 1.3.5.
Mặt khác, nếu h = 0 thì
S `e(£ - 2ah) = |F|.
Vậy 5
do ele -a®)] = FI
và ta có điều phải chứng minh.
Kết hợp Bổ đề này với Bổ đề 2.1.2, ta đạt được:
Hệ qua 2.1.4. Cho F là trường hữu hạn với cấp lẻ và A = F32.
khi đó, kA = F,Vk 3 3.
Chứng minh. Thật vậy, với V+ € F, số các cách biểu diễn z thành tổng # = ai + ds +... + day với ứ,...,a, € Ƒ là
—(k-2)
2'* + O,(IFI= FI
Hệ quả này chứng tỏ rằng các tập tổng kA ít nhiều được phân
bố đều với k > 3. Chú ý khi k = 2 ta vẫn chứng minh được rằng 2A = F, nhưng các tập tổng có thể rất không đều, ví dụ, nếu —1 không là bình phương của phần tử nào trong #', thì 0 chỉ có một cách biểu diễn thành tổng của hai phần tit trong F.
Tiếp theo là mot Bo dộ cho thấy: Nếu ệ là một tập con được chọn
“1I|.A|l„; do đó độ lệch Eourier ngẫu nhiên của 4, thì ||P||„ xấp xỉ với tal
giảm một cách tương xứng khi chuyển qua các tập con ngẫu nhiên.
Bồ đề 2.1.5. Cho A là tập hợp cộng tính trong nhóm cộng, hữu hạn Z và 0 < r < 1. Cho B là tập con ngẫu nhiên của A được xác định bằng cách lấy các sự kiện a € B một cách độc lập với xác suất T. Khi đó VÀ > 0 ta có
2 Ao
P(\|Bllu — z|LAll, > Aứ) < 4|Z|max(e* 7)
trong đó
T(1-7)
?:=|Al—~==—.
ứˆ:=|A| KỊP
Ap dung nó với À = Clog?|Z| với Œ đủ lớn, và giả sử rằng
|Alr(1 — 7) > log|Z|
thì ta có
P(|\„ = r||All, + O(ơlog*|Zl)) =1— O(|Z| 1").
Đặc biệt, néu A = Z thi
IBllu=rZ+O (ra _ 25)
với xác suất cao; vì vậy các tập con ngẫu nhiên của Z có khả năng
là rất đều. Chú ý rằng Pz(B) r với xác suất cao. Ứng dụng chủ yếu của độ lệch Fourier là để nghiên cứu về cấp cộng với độ dài 3.