View Single Post
Old 2021-09-02, 18:58   #512
charybdis's Avatar
Apr 2020

10428 Posts

An ideal is a subset of a ring that forms an additive subgroup and is closed under multiplication by arbitrary elements of the ring. But I don't think that's what you wanted

We have an algebraic polynomial f(x), which in this case will be degree 5, and rational polynomial g(x). Our relations are (a,b) pairs for which the algebraic norm b^5*f(a/b) and rational norm b*g(a/b) are both smooth with respect to the chosen bounds. The aim is to find a set of relations for which the products of the algebraic and rational norms are both squares; we therefore need each prime to appear an even number of times in this set on each side. (0 is even of course.)

There is a further complication which is that on the algebraic side two copies of the same prime p count as different if they correspond to different roots of the algebraic polynomial mod p; I think I explained this before. But why is this necessary? The answer is that the algebraic norms are actually being used to represent complex numbers in a certain number field, and it's the product of these numbers that needs to be square. The (prime, root) pairs correspond to *ideals* (in fact prime ideals) of a particular ring inside this number field.

The same is true on the rational side, but the mathematics is much easier because the number field in question is the rational numbers - hence "rational side" - and the ring is the integers. For each prime p, there is a prime ideal of the integers consisting of the multiples of p, and all prime ideals of the integers are of this form. So on the rational side there is no complication with roots; each prime corresponds to a single ideal.

Finding the required set of relations is equivalent to solving a huge system of linear equations mod 2 (i.e. finding linear dependencies of a huge matrix), since we need each ideal to appear an even number of times in our set. The unknowns/variables are "is this relation in the set", which can be either 0 (no) or 1 (yes). There is one equation for each ideal that appears in the relations. Say a particular ideal appears in relations 337, 590 and 4449, and no others. Then the equation will be "is rel 337 in the set" + "is rel 590 in the set" + "is rel 4449 in the set" = 0 (mod 2). The smaller the matrix, the easier it will be to solve.

If an ideal only appears once as a factor in the entire dataset, then the relation it's in can't possibly be part of any set that contains each ideal an even number of times. This relation is called a singleton, and can be removed in filtering (we don't want to get rid of it forever, because if we sieve some more we might find another relation containing the given ideal). After all the singletons have been removed, we will have created new singletons, so we repeat this process until none are left. At this stage, we need there to be more relations (unknowns) than ideals (equations), else we won't be able to solve our system of equations. tasks.filter.required_excess = 0.05 means that CADO will only proceed with filtering if there are 5% more relations than ideals left at this stage. This is useful because if we have a large excess, we can afford to throw out some more (carefully chosen) relations in order to obtain a smaller matrix.

...and of course even this is an oversimplification as I haven't mentioned merging, cycles or quadratic characters. But it should hopefully give some idea of what's going on.

Last fiddled with by charybdis on 2021-09-02 at 19:14
charybdis is offline   Reply With Quote