1CongNghe.Com: Một chứng minh khác cho bất đẳng thức Loomis-Whitney

Friday, April 8, 2011

Một chứng minh khác cho bất đẳng thức Loomis-Whitney

Cái chứng minh dùng entropy của bất đẳng thức Loomis-Whitney rất gọn nhưng hơi … phù thủy. Ta thử một chứng minh khác, cho trường hợp 3 chiều như trong bài lính bắn laser.

Định lý. Cho ba tập hữu hạn $A, B, C \subset \mathbb Z^2$ . Định nghĩa

$S = \{(x,y,z) \ | \ (x,y) \in A, (y, z) \in B, (z, x) \in C\}$

Ta có $|S| \leq \sqrt{|A| \cdot |B| \cdot |C|}$ .

Chứng minh. Gọi các thành viên của là các “tam giác”. Mỗi thành viên của A, B, C là các ứng cử viên cho các cạnh của các tam giác trong . Với một cạnh $(x,y) \in A$ bất kỳ, gọi $S_{(x,y)}$ là tập tất cả các tạm giác trong có (x,y) là một cạnh. Dùng bất đẳng thức Cauchy-Schwarz ta có

$\displaystyle |S|^2 = \left(\sum_{(x,y)\in A} |S_{(x,y)}|\right)^2 \leq |A| \sum_{(x,y)\in A} |S_{(x,y)}|^2$

Định nghĩa d_C(x) là số các sao cho $(z,x) \in C$ và gọi d_B(y) là số các sao cho $(y,z) \in B$ . Dễ thấy rằng $|S_{(x,y)}|^2 \leq d_C(x)c_B(y)$ . Do đó,