Skip to section
Foundationsfor rotation-free search
Section 20 of 5238% of course
Contents
Chapter 4 Section 4.1 62 min

Part III · Construction and proof

The mismatch: diagonals are not matching positions

Compare the pairing rule for a dot product with the pairing rule for convolution.

Start with the behavior, not the magic trick

Chapter 3 handed us a very specific hot-path goal: we need to multiply matching coordinates and add up the D products, but we absolutely don't want to pay for a separate encrypted lane reduction. Before we start rearranging our data, we need to understand the operation the polynomial multiplier is already doing for us.

Think about how you'd add up things in code. When we multiply two lists of coefficients, every input pair contributes to an output position equal to the sum of its input positions. So, output position t collects every single pair whose positions happen to add up to t. That specific collection rule is called convolution. Don't worry if you aren't familiar with signal processing—we only care about how it handles indices here.

Let's put the rules side by side

dot productpair qi with vi

Matching logical coordinates: the two indices have to be exactly equal.

convolution bucket tpair ai with bt−i

Matching physical destination: the two stored positions have to add up to t.

If we store vector v naturally, its coordinate i just sits at polynomial position i. For a single output bucket t to collect our entire dot product, we'd need t−i=i for every coordinate i. Rearranging that gives us t=2i. But t is one fixed output bucket, while i keeps changing! There's no single bucket t that can equal 0, 2, 4, 6, and so on all at the same time.

Worked example

Let's look at D=4 to see the mismatch

At output bucket 3, convolution pairs our query positions 0,1,2,3 with corpus positions 3,2,1,0. So, if we just use natural storage, we end up calculating q₀v₃+q₁v₂+q₂v₁+q₃v₀. That's definitely not the q₀v₀+q₁v₁+q₂v₂+q₃v₃ we wanted! Bucket 0 just gets q₀v₀, and bucket 2 gets q₀v₂+q₁v₁+q₂v₀. No single natural-order bucket manages to catch all four of our matching products.

Try tracing the anti-diagonals yourself

Grab a piece of paper and write query positions down the left side of a 4x4 grid, and corpus positions across the top. Fill in cell (i,r) with its destination sum, i+r. Notice how all the cells with the same destination form an anti-diagonal? Now look at our dot product: we want cells (0,0), (1,1), (2,2), and (3,3). They sit right on the main diagonal, spreading across different anti-diagonals with sums of 0, 2, 4, and 6.

natural order + bucket 3 = reverse-coordinate pairing

Check your understanding

Why can't a single, fixed convolution bucket pair natural-order coordinate i with itself for all i?

Concrete check

If we have natural-order length-3 vectors, which products actually end up in bucket 2?

Section summary

  • A dot product demands that coordinate indices match exactly.
  • A convolution bucket demands that the position sum remains constant.
  • Natural storage just can't make one fixed bucket satisfy that equality for every single coordinate.

Repository layer · second pass

Why does natural order make convolution pair the wrong coordinates?

A dot product wants pairs (i,i). Convolution bucket t wants pairs (i,k) whose positions sum to t. If both vectors use natural order, a matching pair lands at 2i, so different coordinates land in different buckets. The mismatch is purely positional and appears before encryption.

Making a tiny multiplication grid is the fastest diagnostic. Mark the dot-product cells on the main diagonal and a convolution bucket on an anti-diagonal. No fixed anti-diagonal contains the whole main diagonal.

Reasoning chain

  1. 1

    Write the desired relation k=i.

  2. 2

    Write the available grouping relation i+k=t.

  3. 3

    Substitute k=i.

  4. 4

    Observe t=2i varies with i.

  5. 5

    Conclude that storage, not arithmetic values, must change.

Worked trace

Three matching pairs, three destinations

  1. For D=3, matching pairs are (0,0),(1,1),(2,2).
  2. Their sums are 0,2,4.
  3. No one bucket receives all three.
  4. Adding a bucket cannot recover products it never received.

Result. Natural-order convolution does not perform the desired reduction.

Executable lens · Python

Make the hidden state visible

d = 3
matching_destinations = [i + i for i in range(d)]
assert matching_destinations == [0, 2, 4]
assert len(set(matching_destinations)) != 1

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Blaming encryption for a mismatch present in integer polynomials.
  • Assuming the middle convolution bucket is automatically a dot product.

Retrieval and transfer

Close the book first

  1. Draw D=4 and color diagonal versus anti-diagonal cells.
  2. Prove no fixed t equals 2i for two distinct i.
  3. State which operand’s storage you are free to redesign.