Estimating the Gowers Norm of Modulo Functions over Prime Fields

• KAWACHI Akinori

  Tokyo Institute of Technology

• TANAKA Hidetoki

  Tokyo Institute of Technology

• WATANABE Osamu

  Tokyo Institute of Technology

抄録

We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E95-D (3), 755-762, 2012

  一般社団法人 電子情報通信学会

キーワード

• Gowers norm
• Modulo functions

詳細情報

• CRID: 1390282679355129216
• NII論文ID: 10030611565
• NII書誌ID: AA10826272
• DOI: 10.1587/transinf.e95.d.755
• BIBCODE: 2012IEITI..95..755K
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E95.D/3/E95.D_3_755/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可