1B-2
素体上多項式に対する計算困難な関数
○田中秀宗（東工大），Andrej Bogdanov（The Chinese University of Hong Kong），河内亮周（東工大）
本論文で，我々は素体上多項式に対する新たな困難線増幅を提案する．
すなわち，ある関数が任意の低次多項式で近似することがやや困難であるとき，
その関数の複数個の和は，低次多項式で近似することが非常に難しいことを我々は示した．
この結果は，Viola と Wigderson によって示された，二元体上の多項式に対する
XOR 補題の一般化である．本研究における我々の主な貢献は，
素体上の Gowers ノルムを解析したことである．この解析中で，我々は素体上の
多項式に対する一般化低次数テストである，Gowers テストについて論じた．これは Alon，Kaufman，Krivelevich，Litsyn，Ron らによって与えられた二元体上の低次数テストの，
自然な一般化となっている．この Gowers テストは素体上の Gowers ノルムを解析するための
新しいテクニックである．この議論を用いて，我々は素体上の低次多項式に対する
剰余関数の難しさも示した．