p3_air/symbolic/
variable.rs

1use core::marker::PhantomData;
2
3use serde::{Deserialize, Serialize};
4
5/// Entry kinds for base-field trace columns and public inputs.
6#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
7pub enum BaseEntry {
8    Preprocessed { offset: usize },
9    Main { offset: usize },
10    Periodic,
11    Public,
12}
13
14/// Entry kinds for extension-field columns (permutation trace, challenges, and permutation values).
15#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
16pub enum ExtEntry {
17    Permutation { offset: usize },
18    Challenge,
19    PermutationValue,
20}
21
22/// A variable within the evaluation window for base-field columns.
23#[derive(Copy, Clone, Debug, Serialize, Deserialize)]
24pub struct SymbolicVariable<F> {
25    pub entry: BaseEntry,
26    pub index: usize,
27    #[serde(skip)]
28    pub(crate) _phantom: PhantomData<F>,
29}
30
31impl<F> SymbolicVariable<F> {
32    pub const fn new(entry: BaseEntry, index: usize) -> Self {
33        Self {
34            entry,
35            index,
36            _phantom: PhantomData,
37        }
38    }
39
40    pub const fn degree_multiple(&self) -> usize {
41        match self.entry {
42            // Periodic columns are bounded by degree 1 here; the exact, trace-size-aware
43            // degree is computed by [`Self::poly_degree`].
44            BaseEntry::Preprocessed { .. } | BaseEntry::Main { .. } | BaseEntry::Periodic => 1,
45            BaseEntry::Public => 0,
46        }
47    }
48
49    /// Returns the exact degree of the polynomial this variable resolves to over a
50    /// trace of length `trace_len`, given the period of each periodic column
51    /// (indexed by periodic column index).
52    ///
53    /// Unlike [`Self::degree_multiple`], which measures degree in multiples of the
54    /// degree-`(trace_len - 1)` trace polynomials, this returns the absolute
55    /// polynomial degree, so it accounts for the reduced degree of periodic columns.
56    pub fn poly_degree(&self, trace_len: usize, periodic_periods: &[usize]) -> usize {
57        match self.entry {
58            BaseEntry::Preprocessed { .. } | BaseEntry::Main { .. } => trace_len.saturating_sub(1),
59            BaseEntry::Periodic => {
60                // A periodic column of period `p` (with `p | trace_len`) is the evaluation
61                // of `f'(X) = f(X^(trace_len/p))` with `deg f < p`, so its degree is
62                // `(p - 1) * (trace_len / p) = trace_len - trace_len / p`.
63                let period = periodic_periods
64                    .get(self.index)
65                    .copied()
66                    .unwrap_or(trace_len)
67                    .min(trace_len);
68                match period {
69                    0 => trace_len.saturating_sub(1),
70                    p => trace_len - trace_len / p,
71                }
72            }
73            BaseEntry::Public => 0,
74        }
75    }
76}
77
78/// A variable within the evaluation window for extension-field columns.
79#[derive(Copy, Clone, Debug, Serialize, Deserialize)]
80pub struct SymbolicVariableExt<F, EF> {
81    pub entry: ExtEntry,
82    pub index: usize,
83    #[serde(skip)]
84    pub(crate) _phantom: PhantomData<(F, EF)>,
85}
86
87impl<F, EF> SymbolicVariableExt<F, EF> {
88    pub const fn new(entry: ExtEntry, index: usize) -> Self {
89        Self {
90            entry,
91            index,
92            _phantom: PhantomData,
93        }
94    }
95
96    pub const fn degree_multiple(&self) -> usize {
97        match self.entry {
98            ExtEntry::Permutation { .. } => 1,
99            ExtEntry::Challenge | ExtEntry::PermutationValue => 0,
100        }
101    }
102
103    /// Returns the exact polynomial degree of this extension variable over a trace
104    /// of length `trace_len`. See [`SymbolicVariable::poly_degree`].
105    pub const fn poly_degree(&self, trace_len: usize) -> usize {
106        match self.entry {
107            ExtEntry::Permutation { .. } => trace_len.saturating_sub(1),
108            ExtEntry::Challenge | ExtEntry::PermutationValue => 0,
109        }
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use p3_baby_bear::BabyBear;
116    use p3_field::extension::BinomialExtensionField;
117
118    use super::*;
119
120    type F = BabyBear;
121    type EF = BinomialExtensionField<F, 4>;
122
123    #[test]
124    fn symbolic_variable_new_main() {
125        // A main trace variable preserves its offset and column index.
126        let var = SymbolicVariable::<F>::new(BaseEntry::Main { offset: 1 }, 3);
127        assert_eq!(var.entry, BaseEntry::Main { offset: 1 });
128        assert_eq!(var.index, 3);
129    }
130
131    #[test]
132    fn symbolic_variable_new_preprocessed() {
133        // A preprocessed trace variable preserves its offset and column index.
134        let var = SymbolicVariable::<F>::new(BaseEntry::Preprocessed { offset: 0 }, 5);
135        assert_eq!(var.entry, BaseEntry::Preprocessed { offset: 0 });
136        assert_eq!(var.index, 5);
137    }
138
139    #[test]
140    fn symbolic_variable_new_public() {
141        // A public input variable has no offset, only a column index.
142        let var = SymbolicVariable::<F>::new(BaseEntry::Public, 2);
143        assert_eq!(var.entry, BaseEntry::Public);
144        assert_eq!(var.index, 2);
145    }
146
147    #[test]
148    fn symbolic_variable_degree_multiple_main() {
149        // Main trace columns contribute degree 1.
150        let var = SymbolicVariable::<F>::new(BaseEntry::Main { offset: 0 }, 0);
151        assert_eq!(var.degree_multiple(), 1);
152    }
153
154    #[test]
155    fn symbolic_variable_degree_multiple_preprocessed() {
156        // Preprocessed trace columns contribute degree 1.
157        let var = SymbolicVariable::<F>::new(BaseEntry::Preprocessed { offset: 0 }, 0);
158        assert_eq!(var.degree_multiple(), 1);
159    }
160
161    #[test]
162    fn symbolic_variable_degree_multiple_public() {
163        // Public inputs are constant so they contribute degree 0.
164        let var = SymbolicVariable::<F>::new(BaseEntry::Public, 0);
165        assert_eq!(var.degree_multiple(), 0);
166    }
167
168    #[test]
169    fn symbolic_variable_ext_new_permutation() {
170        // A permutation variable preserves its offset and column index.
171        let var = SymbolicVariableExt::<F, EF>::new(ExtEntry::Permutation { offset: 1 }, 7);
172        assert_eq!(var.entry, ExtEntry::Permutation { offset: 1 });
173        assert_eq!(var.index, 7);
174    }
175
176    #[test]
177    fn symbolic_variable_ext_new_challenge() {
178        // A challenge variable has no offset, only an index.
179        let var = SymbolicVariableExt::<F, EF>::new(ExtEntry::Challenge, 4);
180        assert_eq!(var.entry, ExtEntry::Challenge);
181        assert_eq!(var.index, 4);
182    }
183
184    #[test]
185    fn symbolic_variable_poly_degree_main_and_preprocessed() {
186        // Main and preprocessed columns are degree-`(N - 1)` trace polynomials.
187        let main = SymbolicVariable::<F>::new(BaseEntry::Main { offset: 1 }, 0);
188        let prep = SymbolicVariable::<F>::new(BaseEntry::Preprocessed { offset: 0 }, 0);
189        assert_eq!(main.poly_degree(8, &[]), 7);
190        assert_eq!(prep.poly_degree(8, &[]), 7);
191    }
192
193    #[test]
194    fn symbolic_variable_poly_degree_public_is_constant() {
195        // Public inputs are constants, regardless of trace length.
196        let var = SymbolicVariable::<F>::new(BaseEntry::Public, 0);
197        assert_eq!(var.poly_degree(8, &[]), 0);
198    }
199
200    #[test]
201    fn symbolic_variable_poly_degree_periodic() {
202        // A periodic column of period `p` over a trace of length `N` has degree
203        // `N - N / p`, strictly below the `N - 1` of a regular column for `p < N`.
204        let var = SymbolicVariable::<F>::new(BaseEntry::Periodic, 0);
205        // Period 2 over N = 8: degree 8 - 4 = 4.
206        assert_eq!(var.poly_degree(8, &[2]), 4);
207        // Period 4 over N = 8: degree 8 - 2 = 6.
208        assert_eq!(var.poly_degree(8, &[4]), 6);
209        // Period equal to N behaves like a regular column: degree N - 1.
210        assert_eq!(var.poly_degree(8, &[8]), 7);
211        // Period 1 is a true constant column: degree 0.
212        assert_eq!(var.poly_degree(8, &[1]), 0);
213    }
214
215    #[test]
216    fn symbolic_variable_poly_degree_periodic_missing_period_is_conservative() {
217        // With no period recorded for the column, fall back to a full-degree column.
218        let var = SymbolicVariable::<F>::new(BaseEntry::Periodic, 3);
219        assert_eq!(var.poly_degree(8, &[]), 7);
220    }
221
222    #[test]
223    fn symbolic_variable_ext_poly_degree() {
224        // Permutation columns are degree-`(N - 1)` polynomials; challenges are constants.
225        let perm = SymbolicVariableExt::<F, EF>::new(ExtEntry::Permutation { offset: 0 }, 0);
226        let challenge = SymbolicVariableExt::<F, EF>::new(ExtEntry::Challenge, 0);
227        assert_eq!(perm.poly_degree(8), 7);
228        assert_eq!(challenge.poly_degree(8), 0);
229    }
230
231    #[test]
232    fn symbolic_variable_ext_degree_multiple_permutation() {
233        // Permutation columns contribute degree 1.
234        let var = SymbolicVariableExt::<F, EF>::new(ExtEntry::Permutation { offset: 0 }, 0);
235        assert_eq!(var.degree_multiple(), 1);
236    }
237
238    #[test]
239    fn symbolic_variable_ext_degree_multiple_challenge() {
240        // Challenges are random constants so they contribute degree 0.
241        let var = SymbolicVariableExt::<F, EF>::new(ExtEntry::Challenge, 0);
242        assert_eq!(var.degree_multiple(), 0);
243    }
244}
p3_air/symbolic/variable.rs

p3_air/symbolic/
variable.rs
