Chapter 3Lattices and Learning With Errors

Vectors and the Plane

August 25, 20265 min readbeginner

Everything in this chapter is built out of one object, and it is a very simple one. This note introduces it and the three things you can do with it.

Everything in this chapter is built out of one object, and it is a very simple one. This note introduces it and the three things you can do with it. If you have met vectors before, skim to the last section, which sets up the notation the rest of the chapter uses.

01.A vector is a list of numbers

A vector is an ordered list of numbers. That is the entire definition.

Write v=(3,1)v = (3, 1). This is a vector with two entries, called its components. The number of components is the dimension. So (3,1)(3, 1) is two-dimensional, (5,11,2)(5, 11, 2) is three-dimensional, and a list of 256256 numbers is a 256256-dimensional vector.

The set of all two-dimensional vectors whose entries are real numbers is written R2\mathbb{R}^2. Similarly R3\mathbb{R}^3, and in general Rn\mathbb{R}^n. The notation is doing exactly what it looks like: R\mathbb{R} from Sets and Notation is the real numbers, and the exponent counts how many of them are in the list.

In two dimensions a vector has a picture. Read (3,1)(3, 1) as an instruction: go three units right, then one unit up. That lands you at a point, and the vector is drawn as an arrow from the origin to it. The picture is genuinely helpful, and it is also the thing that stops being available in dimension 256256, which is worth remembering every time this chapter draws something.

02.Adding vectors

To add two vectors, add their components separately. Nothing else happens.

(3,1)+(1,2)  =  (3+1,  1+2)  =  (4,3).(3, 1) + (1, 2) \;=\; (3 + 1,\; 1 + 2) \;=\; (4, 3).

Geometrically this is the instruction-following you would guess. Walk three right and one up, then from wherever you are walk one right and two up. You end at four right and three up.

Two things follow immediately and will be used constantly. The order does not matter, since (1,2)+(3,1)=(4,3)(1,2) + (3,1) = (4,3) as well. And the vector (0,0)(0, 0), called the zero vector, changes nothing when added.

03.Scaling vectors

To multiply a vector by a single number, multiply every component by it. A single number in this context is called a scalar, to distinguish it from a vector.

3⋅(1,2)  =  (3⋅1,  3⋅2)  =  (3,6).3 \cdot (1, 2) \;=\; (3 \cdot 1,\; 3 \cdot 2) \;=\; (3, 6).

Geometrically, scaling by 33 stretches the arrow to three times its length in the same direction. Scaling by −1-1 flips it to point the opposite way:

−1⋅(3,1)  =  (−3,−1).-1 \cdot (3, 1) \;=\; (-3, -1).

Scaling by 00 collapses any vector to (0,0)(0,0).

Subtraction is these two operations combined. To compute v−wv - w, scale ww by −1-1 and add:

(3,1)−(1,2)  =  (3,1)+(−1,−2)  =  (2,−1).(3, 1) - (1, 2) \;=\; (3, 1) + (-1, -2) \;=\; (2, -1).

04.Linear combinations

Now put both operations together, and you have the only construction this chapter actually needs.

Given two vectors b1b_1 and b2b_2, and two scalars x1x_1 and x2x_2, the vector

x1b1+x2b2x_1 b_1 + x_2 b_2

is called a linear combination of b1b_1 and b2b_2. Scale each one, add the results.

Take b1=(3,1)b_1 = (3, 1) and b2=(1,2)b_2 = (1, 2) and work a few by hand.

With x1=1x_1 = 1, x2=0x_2 = 0, the combination is just b1=(3,1)b_1 = (3,1).

With x1=1x_1 = 1, x2=1x_2 = 1:

1⋅(3,1)+1⋅(1,2)  =  (3,1)+(1,2)  =  (4,3).1 \cdot (3,1) + 1 \cdot (1,2) \;=\; (3,1) + (1,2) \;=\; (4,3).

With x1=2x_1 = 2, x2=−1x_2 = -1:

2⋅(3,1)+(−1)⋅(1,2)  =  (6,2)+(−1,−2)  =  (5,0).2 \cdot (3,1) + (-1) \cdot (1,2) \;=\; (6,2) + (-1,-2) \;=\; (5, 0).

With x1=0.5x_1 = 0.5, x2=0.5x_2 = 0.5:

0.5⋅(3,1)+0.5⋅(1,2)  =  (1.5,0.5)+(0.5,1)  =  (2,1.5).0.5 \cdot (3,1) + 0.5 \cdot (1,2) \;=\; (1.5, 0.5) + (0.5, 1) \;=\; (2, 1.5).

Notice that last one. Allowing fractional scalars produced a point with fractional coordinates. Hold on to that observation, because the next note removes it and that removal is the entire subject of the chapter.

05.Bases

If you let x1x_1 and x2x_2 range over all real numbers, the combinations x1b1+x2b2x_1 b_1 + x_2 b_2 with b1=(3,1)b_1 = (3,1) and b2=(1,2)b_2 = (1,2) produce every single point in the plane. Not most of them. All of them.

That is worth checking rather than believing. Suppose you want to reach (5,0)(5, 0). The computation above already did it, with x1=2x_1 = 2 and x2=−1x_2 = -1. Suppose you want (0,1)(0, 1). Solving

3x1+x2=0,x1+2x2=13x_1 + x_2 = 0, \qquad x_1 + 2x_2 = 1

gives x2=−3x1x_2 = -3x_1 from the first equation, so x1−6x1=1x_1 - 6x_1 = 1, meaning x1=−1/5x_1 = -1/5 and x2=3/5x_2 = 3/5. Fractional, but perfectly legal.

When a set of vectors can reach every point of the space by linear combination, and no vector in the set is redundant, the set is called a basis. The pair b1=(3,1)b_1 = (3,1), b2=(1,2)b_2 = (1,2) is a basis of R2\mathbb{R}^2.

"No vector is redundant" has a precise name, linear independence, and in two dimensions it means exactly one thing: the two vectors do not lie along the same line. If b2b_2 were (6,2)(6, 2), which is 2b12 b_1, then every combination would stay on that one line and the plane would be unreachable.

The most familiar basis of R2\mathbb{R}^2 is e1=(1,0)e_1 = (1, 0) and e2=(0,1)e_2 = (0, 1), called the standard basis, because reaching (a,b)(a, b) needs only ae1+be2a e_1 + b e_2 and the coefficients are the coordinates themselves.

Two facts to carry forward. A space has many different bases, not one. And the number of vectors in a basis is always the dimension, so every basis of R2\mathbb{R}^2 has exactly two vectors.

The next note changes one word in the definition of linear combination, and the plane turns into something with gaps in it.

FeedbackBook mode
post-quantum-cryptographycryptographymathematics