Studio protocol
Try using a hand-drawn multiplication table for the first few problems. Label the rows by i, the columns by k, and write i+k in each cell. It makes routing errors instantly obvious.
Part A · powers and polynomials
1. Simplify x⁴x³ and explain the exponent rule.
x⁷. The first factor gives you four copies of x, the second gives you three. Together, that's seven total copies.
2. Convert [2, 0, −1, 5] into a polynomial.
2 − x² + 5x³. You can safely omit the zero term at position 1 from the written expression.
3. Convert 7 − 3x + x⁴ into a length-6 list.
[7, −3, 0, 0, 1, 0].
Part B · multiplication and convolution
4. Multiply (1+x)(1−x) by distributing every possible pair.
1 − x + x − x² = 1 − x².
5. Convolve [1, 2] with [3, 4, 5].
Bucket 0: 3. Bucket 1: 4+6=10. Bucket 2: 5+8=13. Bucket 3: 10. The result is [3, 10, 13, 10].
6. List every pair that contributes to output bucket 3.
All valid (i,k) pairs where i+k=3: (0,3), (1,2), (2,1), and (3,0). Just make sure to omit any pair where an index is outside its input list.
Part C · boundaries
7. Using N=8, route the destinations 6, 8, 11, and 15 negacyclically.
6 stays right at 6 with its normal sign. 8 wraps to 0 and gets negated. 11 wraps to 3 and gets negated. 15 wraps to 7 and gets negated.
8. A direct contribution of +9 and a wrapped ordinary contribution of +4 both reach fixed bucket 2. What value is actually stored?
9 − 4 = 5. Remember, wrapped contributions enter with a minus sign.
9. Explain the difference between cyclic and negacyclic wrap in one sentence.
Both rules subtract N from an over-boundary position, but only negacyclic wrap actually flips the value's sign.
Part D · implementation reasoning
10. For lengths 5 and 3, how many pair products are calculated, and how many linear output buckets are there?
There are 5 × 3 = 15 pair products generated, and they fall into 5 + 3 − 1 = 7 output buckets.
11. Name two fast property tests you can use to verify a convolution implementation.
Check that a ∗ [1] = a, and that a ∗ b = b ∗ a. These don't replace rigorous example-based tests, but they're great at catching broad routing errors.
12. For L=3, M=4, and bucket t=4, derive the valid range for i.
max(0, 4−4+1) = 1 through min(2, 4) = 2. So the only valid pairs are (1,3) and (2,2).
13. Explain why a fixed bucket t equals ordinary cₜ − cₜ₊ᴺ.
Direct products destined for t keep their original sign. Products destined for t+N wrap back to t but change sign, so their ordinary sum ends up being subtracted.
Chapter synthesis problem
Let A=[2, −1, 1] and B=[1, 3, −2]. Grab some paper. Build a nine-record pair table, group those records into five ordinary buckets, and then reduce the result negacyclically using N=3. Don't start from a memorized formula here: make sure all the destinations are visible.
Show me the synthesis trace
The ordinary convolution is [2, 5, −6, 5, −2]. For N=3, fixed bucket 0 becomes 2−5 = −3. Bucket 1 becomes 5−(−2) = 7. Bucket 2 is just −6. So the negacyclic result is [−3, 7, −6]. Recomputing this directly from pair destinations should give you the exact same answer.
Cumulative mastery check
Mastery 1 of 4
Why do product destinations simply use i+k?
Mastery 2 of 4
What exactly does one convolution bucket contain?
Mastery 3 of 4
Which operation specifically uses matching indices and then returns one single number?
Mastery 4 of 4
Under xᴺ = −1, what happens to xᴺ⁺ᵏ?
Chapter 2 complete
You now have the machinery, without an application attached
You can effortlessly represent lists as polynomial coefficients, multiply every pair, route products by index sum, name that operation convolution, and safely reason about fixed-length sign-flipping wrap. The next chapter is going to introduce a problem that desperately needs exactly these tools—and you'll be ready for it.
Repository layer · second pass
Can you account for every product before and after reduction?
This studio closes the foundations by connecting five representations: coefficient lists, polynomial notation, a pair matrix, linear-convolution buckets, and fixed-length negacyclic storage. The values should be chosen last; the positional trace should work for arbitrary coefficients.
A reliable reference model keeps both the ordinary destination and the reduced destination. That trace becomes evidence when an optimized transform or hardware pipeline disagrees. Never let the fast implementation be the only description of expected behavior.
Reasoning chain
- 1
Predict output shape.
- 2
Enumerate every pair.
- 3
Group by ordinary degree.
- 4
Apply the boundary rule separately.
- 5
Compare totals coefficient by coefficient.
- 6
Test the maximum possible degree and all-zero edges.
Worked trace
Build an audit record
- Use two length-four inputs in N=4.
- Record sixteen pair rows.
- Compute linear buckets 0 through 6.
- Reduce buckets 4,5,6 into 0,1,2 with negative signs.
Result. The audit explains both the stored answer and every sign entering it.
Executable lens · Python
Make the hidden state visible
def negacyclic(a, b, n):
out, trace = [0] * n, []
for i, left in enumerate(a):
for k, right in enumerate(b):
degree = i + k
pos, sign = degree % n, (-1 if (degree // n) % 2 else 1)
out[pos] += sign * left * right
trace.append((i, k, degree, pos, sign))
return out, traceRetype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Testing only inputs whose high coefficients are zero.
- Comparing a reduced result directly with unreduced linear convolution.
Retrieval and transfer
Close the book first
- Construct the full trace for [1,2,3,4] times [2,0,−1,1] in N=4.
- Find a pair that lands at the same stored position as a nonwrapped pair.
- Write three assertions that distinguish cyclic from negacyclic code.