PUMaC 2008 · 加试

PUMaC 2008-9 Power Test 1 Forms and Landscapes 2 2 An integer-valued quadratic form is a polynomial (in two variables) of the form f ( x, y ) = ax + hxy + by , where a , h , and b are integers. Since this is the only type of quadratic form we are going to deal with, we will just call them forms. Note that f ( x, y ) = f ( − x, − y ). A form corresponds to a landscape , which is a picture split into regions. To draw one, we start with these three regions, and label them with the specified values of the form. f(1,0) f(1,1) f(0,1) Now we can expand the picture in any direction according to the following rule: If f ( x , y ) and f ( x , y ) are in 1 1 2 2 the regions to either side of an edge, then f ( x + x , y + y ) and f ( x − x , y − y ) are in the regions on either 1 2 1 2 1 2 1 2 end. For example, in the above picture, f (0 , 1) and f (1 , 0) are to either side of the horizontal edge, so f (1 , 1) and f ( − 1 , 1) are on either end. f (1 , 1) is already on the right end, so f ( − 1 , 1) is on the other end. f(1,0) f(-1,1) f(1,1) f(0,1) Similarly, f (1 , 1) and f (1 , 0) are to either side of another edge, so on the opposite ends of it are f (2 , 1) and f (0 , 1). We know which end f (0 , 1) is on, so f (2 , 1) is on the other end: f(2,1) f(1,0) f(1,1) f(-1,1) f(0,1) 1

Again, f ( − 1 , 1) and f (0 , 1) are on either side of an edge, so we expect to find f ( − 1 , 2) and f ( − 1 , 0) on the ends. But f (1 , 0) is already on the end! This isn’t a problem, since f ( − 1 , 0) = f (1 , 0) for any form f . So, we think of f ( x, y ) and f ( − x, − y ) as the same thing. So, f ( − 1 , 2) (or f (1 , − 2)) goes on the other end: f(2,1) f(1,0) f(1,1) f(-1,1) f(0,1) f(-1,2) Here it is expanded a bit: f(-5,3) f(-3,1) f(-2,1) f(-3,2) f(1,0) f(2,1) f(-1,1) f(1,1) f(-1,2) f(0,1) f(2,3) f(1,2) f(1,3) f(2,5) It turns out that for every pair of relatively prime integers a and b , f ( a, b ) (or f ( − a, − b )) occurs exactly once on the landscape. You may use this fact witout proof. 2

2 2 Now taking an actual example form and filling in the values, f ( x, y ) = 6 x + 5 xy − 3 y , the corresponding section of the landscape is: 48 36 11 12 6 31 -2 8 -16 -3 27 4 -6 -1 2 2 Question 1.1: Draw the same section of the landscape for the form x + 2 xy − 3 y Question 1.2: Give the form for which the following is the same section of the landscape. 61 21 9 24 4 41 5 21 24 9 145 56 109 321 3

2 The Arithmetic Progression Conveniently, for any form f 1 f ( x , y ) + f ( x , y ) = ( f ( x + x , y + y ) + f ( x − x , x − y )) (1) 1 1 2 2 1 2 1 2 1 2 1 2 2 Rearranging a little, we get ( f ( x , y ) + f ( x , y )) − f ( x − x , x − y ) = 1 1 2 2 1 2 1 2 f ( x + x , y + y ) − ( f ( x , y ) + f ( x , y )) 1 2 1 2 1 1 2 2 In other words, the numbers f ( x − x , x − y ), ( f ( x , y ) + f ( x , y )), f ( x + x , y + y ) make an arithmetic 1 2 1 2 1 1 2 2 1 2 1 2 progression. 2 2 This makes it much easier to draw landscapes. Say I start with the form f ( x, y ) = 3 x + 2 xy + 4 y : 3 9 4 If I want to fill in the value x to the left of the horizontal edge, I know that x , 3 + 4, and 9 make an arithmetic progression. So, x = 5. 3 5 9 4 If I want to fill in the value y to the top right, I know that 4, 3+9, and y make an arithmetic progression. So, y must be 20. 20 3 9 5 4 The arithmetic progression shows that the values in any three regions which share a vertex determine the rest of the landscape. We say that two forms are equivalent if you can line up their landscapes so that the values in the regions are the same. 4

2 2 2 2 For example, the form f ( x, y ) = 6 x + 5 xy − 3 y and the form g ( x, y ) = 11 x + 19 xy + 6 y are equivalent. Here are sections of their landscapes: 88 73 36 11 6 12 31 -2 8 -3 -16 4 88 12 11 36 -2 73 -16 6 -3 8 31 4 However, if the landscape of one form is just the reflection of that of another, then we don’t consider the forms 2 2 2 2 to be equivalent. In particular, the forms 3 x − 2 xy + 4 x and 3 x + 2 xy + 4 x are not equivalent. 2 2 2 2 Question 2.1: Are the forms x + y and − x − y equivalent? 2 2 2 2 Question 2.2: Are the forms 3 x + 2 xy + 4 y and 4 x − 2 xy + 3 y equivalent? 2 2 2 2 Question 2.3: Are the forms 5 x − 5 xy + y and x + xy + y equivalent? 2 2 2 2 Question 2.4: Are the forms 88 x + 113 xy + 36 y and 8 x − 33 xy + 31 y equivalent? 2 2 2 2 Question 2.5: Are the forms 90 x + 107 xy + 32 y and 101 x − 341 xy + 288 y equivalent? 2 2 2 Question 2.6: Are the forms 3 x − 2 xy and 4 x − y equivalent? 2 2 2 2 Question 2.7: Are the forms x + xy − 9 y and − x − xy + 9 y equivalent? 2 2 2 2 Question 2.8: Are the forms x + xy − 11 y and − x − xy + 11 y equivalent? 2 2 2 2 Question 2.9: Are the forms x + xy − 12 y and − x − xy + 12 y equivalent? 5

3 Indefinite Forms 2 2 2 The discriminant of a form ax + hxy + by is the value D = h − 4 ab . Question 3.1: Do the following numbers occur as discriminants of forms? (For each number, if yes, give an example, if no, prove it.) 0, 1, 2, 3, -1, -2, -3, 13, -13, 22, -22, 47, -47, 100, -100, 31415, -31415. Question 3.2: Give an easy way to tell if a given integer occurs as the discriminant of a form. Question 3.3: Prove or disprove: if two forms are equivalent, they have the same discriminant. Question 3.4: Prove or disprove: if two forms have the same discriminant, they are equivalent. We say a form is indefinite if it can take on both positive and negative values. A river of a form is a connected chain of edges on its landscape each of which separates a region with a positive value from a region with a negative value, which is not a subset of any other such chain. Question 3.5: Prove or disprove: a form is indefinite if and only if it has a positive discriminant. Question 3.6: Prove or disprove: every indefinite form has a river. Question 3.7: Prove or disprove: every form has at most one river. We call a river periodic if the values to either side of it repeat. The period of a form is how many edges it takes for it to repeat. For example, this river is periodic with period 6. 1 3 1 -5 -2 -2 -5 -5 -6 To make things a little more managable, we’ll draw rivers like this: 1 3 1 -5 -2 -5 -6 -5 -2 We call a positive integer D a periodic discriminant if there is an indefinite form with discriminant D and a periodic river. We call a positive integer D a nonperiodic discriminant if there is an indefinite form with discriminant D and no periodic river. Question 3.8: Prove or disprove: a discriminant can’t be both periodic and nonperiodic. (That is, if one indefinite form of some discriminant has a periodic river, all indefinite forms of that discriminant do.) Question 3.9: What are the nonperiodic discriminants? Prove your answer. Question 3.10: How many forms (up to equivalence) are there for each nonperiodic discriminant? 6

4 Symmetries We can reflect the landscape of a form across or ”through” an edge in that landscape. For example, if we start with 2 2 this landscape, corresponding to the form 4 x + 2 xy + 3 y : 4 12 3 -3 1 -4 -17 -9 The reflection of this landscape across the bold edge is -17 -9 -4 -3 1 3 4 12 And the reflection of that same landscape through the bold edge is 12 4 3 1 -3 -4 -9 -17 A form’s river can be symmetric in several ways. For example, the river pictured below is has two types of symmetry. One given by reflection through an edge on the river (between 1 and -7); one given by reflection across an edge adjacent to the river (between -3 and -3). ↔ ↔ ↔ ↔ 1 2 1 2 -6 -7 -6 -3 -3 -6 -7 -6 -3 -3 The following river is symmetric in a different way. If you rotate the landscape around the center of the edge between 3 and -3, and negate each value, you get the same landscape. 7

↔ x ↔ 1 3 4 9 12 13 12 -12 -13 -12 -9 -4 -3 -1 We call these three types of symmetries of a river (reflection through an edge on the river, reflection across an edge adjacent to it, and rotation around an edge on the river combined with negation) primitive symmetries. In the above form, we consider the two pictured reflections to be the same. Both of the rivers above, then, have exactly two primitive symmetries. Question 4.1: Is there a periodic river with no primitive symmetries? If so, give an example, if not, prove it. Question 4.2: Is there a periodic river with exactly one primitive symmetry? If so, give an example, if not, prove it. Question 4.3: Is there a periodic river with exactly three primitive symmetries? If so, give an example, if not, prove it. Question 4.4: Is there a periodic river that is not equivalent to its negation, its reflection, or its reflection’s negation? If so, give an example. If not, prove it. 8