Finite Fields and Their Applications
Character Sums and Polynomials
1st Edition
Published on 28. May 2013
XI, 274 pages
978-3-11-028360-0 (ISBN)
Description
This book is based on the invited talks of the "RICAM-Workshop on Finite Fields and Their Applications: Character Sums and Polynomials" held at the Federal Institute for Adult Education (BIfEB) in Strobl, Austria, from September 2-7, 2012. Finite fields play important roles in many application areas such as coding theory, cryptography, Monte Carlo and quasi-Monte Carlo methods, pseudorandom number generation, quantum computing, and wireless communication. In this book we will focus on sequences, character sums, and polynomials over finite fields in view of the above mentioned application areas: Chapters 1 and 2 deal with sequences mainly constructed via characters and analyzed using bounds on character sums. Chapters 3, 5, and 6 deal with polynomials over finite fields. Chapters 4 and 9 consider problems related to coding theory studied via finite geometry and additive combinatorics, respectively. Chapter 7 deals with quasirandom points in view of applications to numerical integration using quasi-Monte Carlo methods and simulation. Chapter 8 studies aspects of iterations of rational functions from which pseudorandom numbers for Monte Carlo methods can be derived. The goal of this book is giving an overview of several recent research directions as well as stimulating research in sequences and polynomials under the unified framework of character theory.
More details
Other editions
Additional editions
Pascale Charpin | Alexander Pott | Arne Winterhof
Finite Fields and Their Applications
Character Sums and Polynomials
Book
05/2013
1st Edition
De Gruyter
€209.00
Article exhausted; check different version
Pascale Charpin | Alexander Pott | Arne Winterhof
Finite Fields and Their Applications
Character Sums and Polynomials
Book
05/2013
1st Edition
De Gruyter
€199.95
Shipment within 7-9 days
Complete work / Part of the work
Pascale Charpin | Alexander Pott | Arne Winterhof
Finite Fields and Their Applications
Character Sums and Polynomials
Book
05/2013
1st Edition
De Gruyter
€209.00
Article exhausted; check different version
Persons
Pascale Charpin, INRIA, Le Chesnay, France; Alexander Pott, Otto-von-Guericke-University Magdeburg, Germany; Arne Winterhof, Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria.
Content
1 - Preface [Seite 5]
2 - Character Sums and Polyphase Sequence Families with Low Correlation, Discrete Fourier Transform (DFT), and Ambiguity [Seite 13]
2.1 - 1 Introduction [Seite 13]
2.2 - 2 Basic Definitions and Concepts [Seite 14]
2.2.1 - 2.1 Notations [Seite 14]
2.2.2 - 2.2 Polynomial Functions over Fq [Seite 15]
2.2.3 - 2.3 Characters of Finite Fields [Seite 16]
2.2.4 - 2.4 The Weil Bounds on Character Sums [Seite 16]
2.3 - 3 Correlation, DFT, and Ambiguity Functions [Seite 17]
2.3.1 - 3.1 Operators on Sequences [Seite 17]
2.3.2 - 3.2 Correlation Functions [Seite 18]
2.3.3 - 3.3 Ambiguity Functions [Seite 20]
2.3.4 - 3.4 Convolution and Correlation [Seite 22]
2.3.5 - 3.5 Optimal Correlation, DFT, and Ambiguity [Seite 22]
2.4 - 4 Polyphase Sequences for Three Metrics [Seite 23]
2.4.1 - 4.1 Sequences from the Additive Group of ZN and the Additive Group of Zp [Seite 23]
2.4.1.1 - 4.1.1 Frank-Zadoff-Chu (FZC) Sequences [Seite 23]
2.4.1.2 - 4.1.2 Another Class for Zn [Seite 25]
2.4.1.3 - 4.1.3 Sequences from Fp Additive Characters [Seite 25]
2.4.2 - 4.2 Sequences from Fp Multiplicative Characters [Seite 25]
2.4.3 - 4.3 Sequences from Fq Additive Characters [Seite 27]
2.4.4 - 4.4 Sequences from Fq Multiplicative Characters [Seite 29]
2.4.5 - 4.5 Sequences Defined by Indexing Field Elements Alternatively [Seite 32]
2.5 - 5 Sequences with Low Degree Polynomials [Seite 34]
2.5.1 - 5.1 Methods for Generating Signal Sets from a Single Sequence [Seite 34]
2.5.2 - 5.2 Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.1 - 5.2.1 Fq Additive Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.2 - 5.2.2 Fq Multiplicative Sequences with Low Odd Degree Polynomials [Seite 37]
2.5.3 - 5.3 Sequences from Power Residue and Sidel'nikov Sequences [Seite 38]
2.5.3.1 - 5.3.1 Interleaved Structure of Sidel'nikov Sequences [Seite 38]
2.5.3.2 - 5.3.2 Sequences from Linear and/or Quadratic/Inverse Polynomials [Seite 39]
2.5.4 - 5.4 Sequences from Hybrid Characters [Seite 41]
2.5.4.1 - 5.4.1 Sequences Using Weil Representation and Their Generalizations [Seite 41]
2.5.4.2 - 5.4.2 Generalization to Fq Hybrid Sequences [Seite 42]
2.5.5 - 5.5 A New Construction [Seite 44]
2.6 - 6 Two-Level Autocorrelation Sequences and Double Exponential Sums [Seite 45]
2.6.1 - 6.1 Prime Two-Level Autocorrelation Sequences [Seite 45]
2.6.2 - 6.2 Hadamard Transform, Second-Order Decimation-Hadamard Transform, and Hadamard Equivalence [Seite 46]
2.6.3 - 6.3 Conjectures on Ternary 2-Level Autocorrelation Sequences [Seite 47]
2.7 - 7 Some Open Problems [Seite 49]
2.7.1 - 7.1 Current Status of the Conjectures on Ternary 2-Level Autocorrelation [Seite 49]
2.7.2 - 7.2 Possibility of Multiplicative Sequences with Low Autocorrelation [Seite 50]
2.7.3 - 7.3 Problems in Four Alternative Classes of Sequences and the General Hybrid Construction [Seite 50]
2.8 - 8 Conclusions [Seite 50]
3 - Measures of Pseudorandomness [Seite 55]
3.1 - 1 Introduction [Seite 55]
3.2 - 2 Definition of the Pseudorandom Measures [Seite 56]
3.3 - 3 Typical Values of Pseudorandom Measures [Seite 58]
3.4 - 4 Minimum Values of Pseudorandom Measures [Seite 59]
3.5 - 5 Connection between Pseudorandom Measures [Seite 61]
3.6 - 6 Constructions [Seite 62]
3.7 - 7 Family Measures [Seite 64]
3.8 - 8 Linear Complexity [Seite 66]
3.9 - 9 Multidimensional Theory [Seite 68]
3.10 - 10 Extensions [Seite 69]
4 - Existence Results for Finite Field Polynomials with Specified Properties [Seite 77]
4.1 - 1 Introduction [Seite 77]
4.2 - 2 A Survey of Known Results [Seite 78]
4.2.1 - 2.1 Normal Bases [Seite 79]
4.2.2 - 2.2 Primitive Normal Bases [Seite 80]
4.2.3 - 2.3 Prescribed Coefficients [Seite 82]
4.2.4 - 2.4 Primitive Polynomials: Prescribed Coefficients [Seite 82]
4.2.5 - 2.5 Primitive Normal Polynomials: Prescribed Coefficients [Seite 85]
4.3 - 3 A Survey of Methodology and Techniques [Seite 87]
4.3.1 - 3.1 Basic Approach [Seite 88]
4.3.2 - 3.2 A p-adic Approach to Coefficient Constraints [Seite 90]
4.3.3 - 3.3 The Sieving Technique [Seite 93]
4.4 - 4 Conclusion [Seite 95]
5 - Incidence Structures, Codes, and Galois Geometries [Seite 101]
5.1 - 1 Introduction [Seite 101]
5.2 - 2 Galois Closed Codes [Seite 103]
5.3 - 3 Extension Codes of Simplex and First-Order Reed-Muller Codes [Seite 105]
5.4 - 4 Simple Incidence Structures and Their Codes [Seite 109]
5.5 - 5 Embedding Theorems [Seite 111]
5.6 - 6 Designs with Classical Parameters [Seite 117]
5.7 - 7 Two-Weight Codes [Seite 120]
5.8 - 8 Steiner Systems [Seite 121]
5.9 - 9 Configurations [Seite 123]
5.10 - 10 Conclusion and Open Problems [Seite 125]
6 - Special Mappings of Finite Fields [Seite 129]
6.1 - 1 Introduction [Seite 129]
6.2 - 2 Different Notions for Optimal Non-linearity [Seite 132]
6.2.1 - 2.1 Almost Perfect Nonlinear (APN) Mappings [Seite 133]
6.2.2 - 2.2 Bent and Almost Bent (AB) Mappings [Seite 136]
6.3 - 3 Functions with a Linear Structure [Seite 137]
6.4 - 4 Crooked Mappings [Seite 140]
6.5 - 5 Planar Mappings [Seite 142]
6.6 - 6 Switching Construction [Seite 145]
6.7 - 7 Products of Linearized Polynomials [Seite 149]
7 - On The Classification of Perfect Nonlinear (PN) and Almost Perfect Nonlinear (APN) Monomial Functions [Seite 157]
7.1 - 1 Introduction [Seite 157]
7.2 - 2 Background and Motivation [Seite 158]
7.2.1 - 2.1 PN and Planar Functions [Seite 158]
7.2.2 - 2.2 APN Functions [Seite 160]
7.3 - 3 Outline of APN Functions Classification Proof [Seite 161]
7.3.1 - 3.1 Singularities in APN case [Seite 163]
7.3.2 - 3.2 A Warm-Up Case [Seite 165]
7.4 - 4 PN Functions Classification Proof: Analysis of Singularities [Seite 166]
7.4.1 - 4.1 Singular Points in Case (b.1) [Seite 168]
7.4.2 - 4.2 Singular Points at Infinity [Seite 169]
7.4.3 - 4.3 The Multiplicities [Seite 171]
7.4.4 - 4.4 Further Analysis [Seite 171]
7.4.5 - 4.5 Type(i) [Seite 173]
7.4.6 - 4.6 Type(iii) [Seite 173]
7.4.7 - 4.7 Type(ii) [Seite 173]
7.5 - 5 Case (b.1): Assuming Bt(x,y) Irreducible over Fp [Seite 174]
7.6 - 6 Case (b.1): Assuming Bt (x, y) not Irreducible over Fp [Seite 176]
8 - Finite Fields and Quasirandom Points [Seite 181]
8.1 - 1 Introduction [Seite 181]
8.2 - 2 General Background [Seite 182]
8.3 - 3 General Construction Principles [Seite 185]
8.4 - 4 The Combinatorics of Nets [Seite 189]
8.5 - 5 Duality Theory [Seite 191]
8.6 - 6 Special Constructions of Nets [Seite 193]
8.6.1 - 6.1 Polynomial Lattices [Seite 193]
8.6.2 - 6.2 Hyperplane Nets [Seite 195]
8.6.3 - 6.3 Nets Obtained from Global Function Fields [Seite 197]
8.7 - 7 Special Constructions of (T,s)-Sequences [Seite 199]
8.7.1 - 7.1 Faure Sequences and Niederreiter Sequences-c [Seite 200]
8.7.2 - 7.2 Sequences Obtained from Global Function Fields [Seite 201]
8.7.3 - 7.3 Sequences with Finite-Row Generating Matrices [Seite 204]
9 - Iterations of Rational Functions: Some Algebraic and Arithmetic Aspects [Seite 209]
9.1 - 1 Introduction [Seite 209]
9.1.1 - 1.1 Background [Seite 209]
9.1.2 - 1.2 Notation [Seite 210]
9.1.3 - 1.3 Iterations [Seite 210]
9.2 - 2 Distribution of Elements, Degree Growth and Representation [Seite 211]
9.2.1 - 2.1 Exponential Sums and Linear Combinations of Iterates [Seite 211]
9.2.2 - 2.2 Generic Multivariate Polynomials [Seite 213]
9.2.3 - 2.3 Systems with Slow Degree Growth [Seite 215]
9.2.4 - 2.4 Exponential Degree Growth, but Sparse Representation [Seite 218]
9.2.5 - 2.5 Representation of Iterates [Seite 219]
9.2.6 - 2.6 Deligne and Dwork-Regular Polynomials [Seite 220]
9.2.7 - 2.7 Distribution in Prime and Polynomial Times [Seite 221]
9.3 - 3 Structure of Rational Function Maps [Seite 222]
9.3.1 - 3.1 Trajectory Length and Periodic Structure [Seite 222]
9.3.2 - 3.2 Graph of Rational Function Maps [Seite 224]
9.3.3 - 3.3 Common Composites and Intersection of Orbits [Seite 225]
9.4 - 4 Geometric Properties of Orbits [Seite 227]
9.4.1 - 4.1 Diameter of Orbits [Seite 227]
9.4.2 - 4.2 Convex Hull of Trajectories [Seite 229]
9.5 - 5 Stability, Absolute Irreducibility and Coprimality [Seite 229]
9.5.1 - 5.1 Motivation [Seite 229]
9.5.2 - 5.2 Stable Univariate Polynomials [Seite 230]
9.5.3 - 5.3 On the Growth of the Number of Irreducible Factors [Seite 232]
9.5.4 - 5.4 Stable Multivariate Polynomials [Seite 234]
9.5.5 - 5.5 Coprimality of Iterates [Seite 236]
9.6 - 6 More Problems [Seite 236]
9.6.1 - 6.1 Multiplicative Independence [Seite 236]
9.6.2 - 6.2 Complete Polynomials [Seite 237]
10 - Additive Combinatorics over Finite Fields: New Results and Applications [Seite 245]
10.1 - 1 Introduction [Seite 245]
10.2 - 2 Notation [Seite 247]
10.3 - 3 Estimates from Arithmetic Combinatorics [Seite 248]
10.3.1 - 3.1 Classical Sum-Product Problem [Seite 248]
10.3.2 - 3.2 Multifold Sum-Product Problem [Seite 250]
10.3.3 - 3.3 Sum-Inversion Estimates [Seite 251]
10.3.4 - 3.4 Equations over Finite Fields with Variables from Arbitrary Sets [Seite 253]
10.3.5 - 3.5 Incidence Bounds [Seite 255]
10.3.6 - 3.6 Polynomial and Other Nonlinear Functions on Sets [Seite 257]
10.3.7 - 3.7 Structured Sets [Seite 259]
10.3.8 - 3.8 Elliptic Curve Analogues [Seite 261]
10.3.9 - 3.9 Matrix Analogues [Seite 264]
10.4 - 4 Applications [Seite 265]
10.4.1 - 4.1 Exponential and Character Sums [Seite 265]
10.4.2 - 4.2 Waring, Erdos-Graham and Other Additive Problems in Finite Fields [Seite 268]
10.4.3 - 4.3 Intersections of Almost Arithmetic and Geometric Progressions [Seite 270]
10.4.4 - 4.4 Exponential Congruence [Seite 272]
10.4.5 - 4.5 Hidden Shifted Power Problem [Seite 273]
10.4.6 - Sum-Product Estimates and Multiplicative Orders of . and . + .-1 in Finite Fields [Seite 273]
10.4.7 - 4.7 Expansion of Dynamical Systems [Seite 274]
2 - Character Sums and Polyphase Sequence Families with Low Correlation, Discrete Fourier Transform (DFT), and Ambiguity [Seite 13]
2.1 - 1 Introduction [Seite 13]
2.2 - 2 Basic Definitions and Concepts [Seite 14]
2.2.1 - 2.1 Notations [Seite 14]
2.2.2 - 2.2 Polynomial Functions over Fq [Seite 15]
2.2.3 - 2.3 Characters of Finite Fields [Seite 16]
2.2.4 - 2.4 The Weil Bounds on Character Sums [Seite 16]
2.3 - 3 Correlation, DFT, and Ambiguity Functions [Seite 17]
2.3.1 - 3.1 Operators on Sequences [Seite 17]
2.3.2 - 3.2 Correlation Functions [Seite 18]
2.3.3 - 3.3 Ambiguity Functions [Seite 20]
2.3.4 - 3.4 Convolution and Correlation [Seite 22]
2.3.5 - 3.5 Optimal Correlation, DFT, and Ambiguity [Seite 22]
2.4 - 4 Polyphase Sequences for Three Metrics [Seite 23]
2.4.1 - 4.1 Sequences from the Additive Group of ZN and the Additive Group of Zp [Seite 23]
2.4.1.1 - 4.1.1 Frank-Zadoff-Chu (FZC) Sequences [Seite 23]
2.4.1.2 - 4.1.2 Another Class for Zn [Seite 25]
2.4.1.3 - 4.1.3 Sequences from Fp Additive Characters [Seite 25]
2.4.2 - 4.2 Sequences from Fp Multiplicative Characters [Seite 25]
2.4.3 - 4.3 Sequences from Fq Additive Characters [Seite 27]
2.4.4 - 4.4 Sequences from Fq Multiplicative Characters [Seite 29]
2.4.5 - 4.5 Sequences Defined by Indexing Field Elements Alternatively [Seite 32]
2.5 - 5 Sequences with Low Degree Polynomials [Seite 34]
2.5.1 - 5.1 Methods for Generating Signal Sets from a Single Sequence [Seite 34]
2.5.2 - 5.2 Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.1 - 5.2.1 Fq Additive Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.2 - 5.2.2 Fq Multiplicative Sequences with Low Odd Degree Polynomials [Seite 37]
2.5.3 - 5.3 Sequences from Power Residue and Sidel'nikov Sequences [Seite 38]
2.5.3.1 - 5.3.1 Interleaved Structure of Sidel'nikov Sequences [Seite 38]
2.5.3.2 - 5.3.2 Sequences from Linear and/or Quadratic/Inverse Polynomials [Seite 39]
2.5.4 - 5.4 Sequences from Hybrid Characters [Seite 41]
2.5.4.1 - 5.4.1 Sequences Using Weil Representation and Their Generalizations [Seite 41]
2.5.4.2 - 5.4.2 Generalization to Fq Hybrid Sequences [Seite 42]
2.5.5 - 5.5 A New Construction [Seite 44]
2.6 - 6 Two-Level Autocorrelation Sequences and Double Exponential Sums [Seite 45]
2.6.1 - 6.1 Prime Two-Level Autocorrelation Sequences [Seite 45]
2.6.2 - 6.2 Hadamard Transform, Second-Order Decimation-Hadamard Transform, and Hadamard Equivalence [Seite 46]
2.6.3 - 6.3 Conjectures on Ternary 2-Level Autocorrelation Sequences [Seite 47]
2.7 - 7 Some Open Problems [Seite 49]
2.7.1 - 7.1 Current Status of the Conjectures on Ternary 2-Level Autocorrelation [Seite 49]
2.7.2 - 7.2 Possibility of Multiplicative Sequences with Low Autocorrelation [Seite 50]
2.7.3 - 7.3 Problems in Four Alternative Classes of Sequences and the General Hybrid Construction [Seite 50]
2.8 - 8 Conclusions [Seite 50]
3 - Measures of Pseudorandomness [Seite 55]
3.1 - 1 Introduction [Seite 55]
3.2 - 2 Definition of the Pseudorandom Measures [Seite 56]
3.3 - 3 Typical Values of Pseudorandom Measures [Seite 58]
3.4 - 4 Minimum Values of Pseudorandom Measures [Seite 59]
3.5 - 5 Connection between Pseudorandom Measures [Seite 61]
3.6 - 6 Constructions [Seite 62]
3.7 - 7 Family Measures [Seite 64]
3.8 - 8 Linear Complexity [Seite 66]
3.9 - 9 Multidimensional Theory [Seite 68]
3.10 - 10 Extensions [Seite 69]
4 - Existence Results for Finite Field Polynomials with Specified Properties [Seite 77]
4.1 - 1 Introduction [Seite 77]
4.2 - 2 A Survey of Known Results [Seite 78]
4.2.1 - 2.1 Normal Bases [Seite 79]
4.2.2 - 2.2 Primitive Normal Bases [Seite 80]
4.2.3 - 2.3 Prescribed Coefficients [Seite 82]
4.2.4 - 2.4 Primitive Polynomials: Prescribed Coefficients [Seite 82]
4.2.5 - 2.5 Primitive Normal Polynomials: Prescribed Coefficients [Seite 85]
4.3 - 3 A Survey of Methodology and Techniques [Seite 87]
4.3.1 - 3.1 Basic Approach [Seite 88]
4.3.2 - 3.2 A p-adic Approach to Coefficient Constraints [Seite 90]
4.3.3 - 3.3 The Sieving Technique [Seite 93]
4.4 - 4 Conclusion [Seite 95]
5 - Incidence Structures, Codes, and Galois Geometries [Seite 101]
5.1 - 1 Introduction [Seite 101]
5.2 - 2 Galois Closed Codes [Seite 103]
5.3 - 3 Extension Codes of Simplex and First-Order Reed-Muller Codes [Seite 105]
5.4 - 4 Simple Incidence Structures and Their Codes [Seite 109]
5.5 - 5 Embedding Theorems [Seite 111]
5.6 - 6 Designs with Classical Parameters [Seite 117]
5.7 - 7 Two-Weight Codes [Seite 120]
5.8 - 8 Steiner Systems [Seite 121]
5.9 - 9 Configurations [Seite 123]
5.10 - 10 Conclusion and Open Problems [Seite 125]
6 - Special Mappings of Finite Fields [Seite 129]
6.1 - 1 Introduction [Seite 129]
6.2 - 2 Different Notions for Optimal Non-linearity [Seite 132]
6.2.1 - 2.1 Almost Perfect Nonlinear (APN) Mappings [Seite 133]
6.2.2 - 2.2 Bent and Almost Bent (AB) Mappings [Seite 136]
6.3 - 3 Functions with a Linear Structure [Seite 137]
6.4 - 4 Crooked Mappings [Seite 140]
6.5 - 5 Planar Mappings [Seite 142]
6.6 - 6 Switching Construction [Seite 145]
6.7 - 7 Products of Linearized Polynomials [Seite 149]
7 - On The Classification of Perfect Nonlinear (PN) and Almost Perfect Nonlinear (APN) Monomial Functions [Seite 157]
7.1 - 1 Introduction [Seite 157]
7.2 - 2 Background and Motivation [Seite 158]
7.2.1 - 2.1 PN and Planar Functions [Seite 158]
7.2.2 - 2.2 APN Functions [Seite 160]
7.3 - 3 Outline of APN Functions Classification Proof [Seite 161]
7.3.1 - 3.1 Singularities in APN case [Seite 163]
7.3.2 - 3.2 A Warm-Up Case [Seite 165]
7.4 - 4 PN Functions Classification Proof: Analysis of Singularities [Seite 166]
7.4.1 - 4.1 Singular Points in Case (b.1) [Seite 168]
7.4.2 - 4.2 Singular Points at Infinity [Seite 169]
7.4.3 - 4.3 The Multiplicities [Seite 171]
7.4.4 - 4.4 Further Analysis [Seite 171]
7.4.5 - 4.5 Type(i) [Seite 173]
7.4.6 - 4.6 Type(iii) [Seite 173]
7.4.7 - 4.7 Type(ii) [Seite 173]
7.5 - 5 Case (b.1): Assuming Bt(x,y) Irreducible over Fp [Seite 174]
7.6 - 6 Case (b.1): Assuming Bt (x, y) not Irreducible over Fp [Seite 176]
8 - Finite Fields and Quasirandom Points [Seite 181]
8.1 - 1 Introduction [Seite 181]
8.2 - 2 General Background [Seite 182]
8.3 - 3 General Construction Principles [Seite 185]
8.4 - 4 The Combinatorics of Nets [Seite 189]
8.5 - 5 Duality Theory [Seite 191]
8.6 - 6 Special Constructions of Nets [Seite 193]
8.6.1 - 6.1 Polynomial Lattices [Seite 193]
8.6.2 - 6.2 Hyperplane Nets [Seite 195]
8.6.3 - 6.3 Nets Obtained from Global Function Fields [Seite 197]
8.7 - 7 Special Constructions of (T,s)-Sequences [Seite 199]
8.7.1 - 7.1 Faure Sequences and Niederreiter Sequences-c [Seite 200]
8.7.2 - 7.2 Sequences Obtained from Global Function Fields [Seite 201]
8.7.3 - 7.3 Sequences with Finite-Row Generating Matrices [Seite 204]
9 - Iterations of Rational Functions: Some Algebraic and Arithmetic Aspects [Seite 209]
9.1 - 1 Introduction [Seite 209]
9.1.1 - 1.1 Background [Seite 209]
9.1.2 - 1.2 Notation [Seite 210]
9.1.3 - 1.3 Iterations [Seite 210]
9.2 - 2 Distribution of Elements, Degree Growth and Representation [Seite 211]
9.2.1 - 2.1 Exponential Sums and Linear Combinations of Iterates [Seite 211]
9.2.2 - 2.2 Generic Multivariate Polynomials [Seite 213]
9.2.3 - 2.3 Systems with Slow Degree Growth [Seite 215]
9.2.4 - 2.4 Exponential Degree Growth, but Sparse Representation [Seite 218]
9.2.5 - 2.5 Representation of Iterates [Seite 219]
9.2.6 - 2.6 Deligne and Dwork-Regular Polynomials [Seite 220]
9.2.7 - 2.7 Distribution in Prime and Polynomial Times [Seite 221]
9.3 - 3 Structure of Rational Function Maps [Seite 222]
9.3.1 - 3.1 Trajectory Length and Periodic Structure [Seite 222]
9.3.2 - 3.2 Graph of Rational Function Maps [Seite 224]
9.3.3 - 3.3 Common Composites and Intersection of Orbits [Seite 225]
9.4 - 4 Geometric Properties of Orbits [Seite 227]
9.4.1 - 4.1 Diameter of Orbits [Seite 227]
9.4.2 - 4.2 Convex Hull of Trajectories [Seite 229]
9.5 - 5 Stability, Absolute Irreducibility and Coprimality [Seite 229]
9.5.1 - 5.1 Motivation [Seite 229]
9.5.2 - 5.2 Stable Univariate Polynomials [Seite 230]
9.5.3 - 5.3 On the Growth of the Number of Irreducible Factors [Seite 232]
9.5.4 - 5.4 Stable Multivariate Polynomials [Seite 234]
9.5.5 - 5.5 Coprimality of Iterates [Seite 236]
9.6 - 6 More Problems [Seite 236]
9.6.1 - 6.1 Multiplicative Independence [Seite 236]
9.6.2 - 6.2 Complete Polynomials [Seite 237]
10 - Additive Combinatorics over Finite Fields: New Results and Applications [Seite 245]
10.1 - 1 Introduction [Seite 245]
10.2 - 2 Notation [Seite 247]
10.3 - 3 Estimates from Arithmetic Combinatorics [Seite 248]
10.3.1 - 3.1 Classical Sum-Product Problem [Seite 248]
10.3.2 - 3.2 Multifold Sum-Product Problem [Seite 250]
10.3.3 - 3.3 Sum-Inversion Estimates [Seite 251]
10.3.4 - 3.4 Equations over Finite Fields with Variables from Arbitrary Sets [Seite 253]
10.3.5 - 3.5 Incidence Bounds [Seite 255]
10.3.6 - 3.6 Polynomial and Other Nonlinear Functions on Sets [Seite 257]
10.3.7 - 3.7 Structured Sets [Seite 259]
10.3.8 - 3.8 Elliptic Curve Analogues [Seite 261]
10.3.9 - 3.9 Matrix Analogues [Seite 264]
10.4 - 4 Applications [Seite 265]
10.4.1 - 4.1 Exponential and Character Sums [Seite 265]
10.4.2 - 4.2 Waring, Erdos-Graham and Other Additive Problems in Finite Fields [Seite 268]
10.4.3 - 4.3 Intersections of Almost Arithmetic and Geometric Progressions [Seite 270]
10.4.4 - 4.4 Exponential Congruence [Seite 272]
10.4.5 - 4.5 Hidden Shifted Power Problem [Seite 273]
10.4.6 - Sum-Product Estimates and Multiplicative Orders of . and . + .-1 in Finite Fields [Seite 273]
10.4.7 - 4.7 Expansion of Dynamical Systems [Seite 274]
