Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 3 / i

Solution

f \in F [x_{1}, \dots, x_{n}]

have total degree at most

d_{1} + \dots + d_{n}

, and suppose

[x_{1}^{d_{1}} \dots x_{n}^{d_{n}}] f \neq = 0.

For arbitrary subsets

S_{i} \subseteq F

with

∣ S_{i} ∣ = d_{i} + 1

, there is an

x \in S_{1} \times \dots \times S_{n}

such that

f (x) \neq = 0

For the proof, define

ϕ_{i}^{'} (a) = \prod_{b \in S_{i} ∖ {a}} (a - b) .

Successive Lagrange interpolation in the variables gives the Alon-Tarsi lemma

[x_{1}^{d_{1}} \dots x_{n}^{d_{n}}] f = \sum_{a_{i} \in S_{i}} \frac{f ( a _{1} , \dots , a _{n} )}{\prod _{i} ϕ _{i}^{'} ( a _{i} )} .

Every denominator is nonzero because the elements of

S_{i}

are distinct. If

f

vanished throughout the product grid, the right side and hence the assumed nonzero coefficient would vanish. This contradiction proves the theorem.

There are no discussions about this article yet.

There are currently no matching articles.