Factoring polynomials in finite fields: An application of Lang-Weil to a problem in graph theory (Q920103)

Fix an integer \(n\geq 2\), a finite field k and an extension field \(K=k(\xi)\) of degree n. F. R. K. Chung introduces a directed graph whose nodes are the elements \(\alpha\) of \(K^{\times}\) and in which there is a directed edge \(\alpha\to \beta\) if and only if \(\beta /\alpha =\xi +a\) for some \(a\in k\). Let d be the diameter of the graph. Chung shows for each fixed n there is an explicit constant A(n) such that \(d\leq 2n+1\) provided that \(Card(k)\geq A(n)\) and \(d\geq n+1\) provided \(Card(k)\geq b-n.\) In the paper under review the author proves that there exists an inexplicit constant B(n) such that \(d\leq n+2\) provided Card(k)\(\geq B(n)\). What the author really proves is that every element of \(K^{\times}\) can be written as the product of precisely \(n+2\) distinct factor each in \(\{\xi +a\}_{a\in k}\). The Lang-Weil method of obtaining uniform estimates for the number of rational points on a variety over a finite field so that variety varies in a suitable family is used.