--==================================================================--
-- Notes taken during Dan's Macaulay 2 Extravaganza                 --
--                   (a dialogue)                                   --
--==================================================================--

----------------------------------------------------------------------
-- Day 1                                                            --
----------------------------------------------------------------------

-- Question: What do equations have to do with ideals?

---- Ans 1: roots of an equation generate an ideal

---- Ans 2: ideals give hilbert functions which give numbers

-- Ok can you give me an equation to work with?

---- x^2 + 1 = 0

-- What are the roots of this equation

---- What field are we in?

-- Ok, what field could we be in? 

---- ZZ/p, ZZ/2, CC, QQ[i], ZZ[i], QQ

-- Now evaluate all of these proposals and tell me what equations have
-- to do with ideals

-- Alright, suppose CC is the field, what are the roots?

---- i, -i

-- Do the roots generate an ideal?

-- An ideal is a subset of a ring. What ideal is iCC + (-i)CC?

---- All of CC

-- Back to work: What do equations have to do with ideals.

---- If you mod out by a function it sets it equal to zero - and
---- creates an equation

-- Is "create" the right word? Let's word-smith this sentence.

---- Maybe use "generate" rather than "create"?

-- What are we modding out by?

---- (x^2+1)

-- What ring are we using?

---- Some polynomial ring?

-- Which polynomial ring?

---- RR[x]

-- What do you get?

---- CC[x]

-- Right CC. Let's be more abstract let F be a field and consider R =
-- F[X_1..X_n], and let I = (f_1..f_m). Let x be the image of X in the
-- quotient ring S = R/I. Each n-tuple x is a root of the simultaneous
-- equations f(x) = 0 in S.

---- Replace "create" above with "satisfies"?

-- I was hoping for "imposes" or "enforces" or "decrees"

-- By moding out, we are creating the relation on x, which forces x to
-- be a solution to the polynomial(s) in the ideal. This is a general
-- mechanism.

-- This works in degree 2, does it work in higher degrees? Recall the
-- original question:

-- Question: What do equations have to do with ideals?

-- When you have an equation, say x^2 + 1 = 0, it is not really
-- true. You can make it true by moding out. So there are two things
-- you can do with equations:

-- 1 Impose them 

-- 2 Solve them

-- These represent two dichotomies of what you can do with equations.
-- Now, what do systems of equations have to do with ideals?

-- Give me a system of equations:

---- 2x - 3 = 0 
---- x^2 + 1 = 0

-- Someone give me another system

---- x*y*z = 10
---- x+y+z = 8

-- Ok good. Now we have two systems. Write down the ideals for these
-- systems. I'll add some equations. Then type them into M2 and get
-- the gb for the systems.

R = QQ[x,y,z]
I = ideal(2*x-3,x^2+1)
gens gb I 

J = ideal(x*y*z-10,x+y+z-8)
gens gb J

K = ideal(x^2+1)
gens gb K

L = ideal(x^2+y^2 - 1, x*y+y - 5)
gens gb L

M = ideal(x^2-1,x^3-1)
gens gb M

-- Think about this ideal above

I = ideal(2*x-3,x^2+1)
gens gb I -- What does this mean?

---- we get a different value of x for each of the equations.

-- What are the solutions to the above system? 

---- There are none

-- Over what field?

---- Over any field

-- That might be true

-- The solution set is the empty set. The gb has 1 as a generator. Is
-- there a reason?

-- To clarify the question, consider the relationships between all of
-- the following:

--   Equations ----- Ideal
--          \         /
--        Groebner basis

-- Can you show by hand that the above ideal is generated by 1?

---- 1 = 4/13(x^2+1) - (2*x+3)/13 (2*x-3) 

1 == (4/13)*(x^2+1) - ((2*x+3)/13)*(2*x-3)

-- Assuming this equation is correct, we see that 1 is in the ideal.
-- What does that say about the system of equations having no
-- solution?

---- If there were a solution, could take a linear combination which
---- makes 1 = 0. (Use the formula above)

-- Hence having 1 in the ideal forces that there are no
-- solutions. So how does the computer get the answer?

---- Euclidean algorithm

-- Everybody use the Euclidean algorithm on this. When you are done,
-- see if you can explain M2's output for the ideal M above.

M = ideal(x^2-1,x^3-1)
gens gb M

-- Euclidean Algorithm: f,g elements of F[x]

-- Step: f = ax^m + ...
--       g = bx^n + ...
--       f = f_0
--       g = g_0
--       m<= n
--       replace g by g = b/a x^{n-m} f          (a != 0 and b != 0)
--       repeat
--
-- Eventually g = 0 and f generates (f_0,g_0)

-- The Euclidean algorithm gives an equivalent system of equations
-- that have the same roots. Moreover, it can give a method of
-- deciding whether ideals are equal.

-- What's the connection between equations and ideals? Well if f = 0,
-- then h*f = 0. Also if g = 0, then f+g = 0.

-- Now think about the properties of ideals. If f and g are elements
-- of I, h*f is in I and f+g is in I.

-- With a little work we see that in a polynomial ring two systems of
-- generators of an ideal are solved by the same system of equations.

-- Look at 

L = ideal(x^2+y^2 - 1, x*y+y - 5)
gens gb L

-- Compute the solution with Mathematica. Here is the code:

-- Solve[{x^2+y^2-1 == 0,x*y+y-5 == 0},x,y]

-- What are these equations?

-- x^2+y^2 = 1 (a circle)
-- x*y+y = 5   (a hyperbola)

-- Now how many solutions are there? You can put a decimal point after
-- one of the numbers, this will make Mathematica solve the equation
-- numerically, and let you see how many solutions there are
-- easier. But how do you do it algebraically? That's what I'm most
-- interested in.

-- We need a black book for solving single equations. We'll use
-- quotient rings.

-- CC = RR[x]/(x^2 + 1)

-- This gives us one root. Of course instead of creating roots, you
-- may wish to find roots. So suppose you have a black box which gives
-- you one root of x^n + ... = 0. Of course this polynomial has n
-- roots.

---- Looking at gb's Lex order seems helpful. Try the following
---- example changing the order

R = QQ[x,y, MonomialOrder => Lex]
L = ideal(x^2+y^2 - 1, x*y+y - 5)
gens gb L

R = QQ[x,y, MonomialOrder => GLex]
L = ideal(x^2+y^2 - 1, x*y+y - 5)
gens gb L

R = QQ[x,y]
L = ideal(x^2+y^2 - 1, x*y+y - 5)
gens gb L

---- When you look at the gb with the Lex ordering, we get a 4th
---- degree polynomial in y. So maybe that corresponds to the fact
---- that we have 4 solutions.

-- Ok try to convince your neighbor that this is true.

---- Well, in the Lex ordering, we have that the first generator is of
---- degree 4. The second generator is of degree 1. Hence there are a
---- total of 4 solutions.

-- FYI: Maple code to see the plots:

-- with(plots,implicitplot);
-- implicitplot([x^2+y^2-1,x*y+y-5],x=-5..5,y = -5..5);

-- Note that from this plot we see that all roots are in the complex
-- plane.

-- Now consider this diagram:

--              Equations ----- Ideal
--              /       \         /
--      Factoring     Groebner basis

-- We want to know the connection between the entries of the above
-- diagram. Consider the polynomial

-- x^2 + bx + c = 0
--       ||
-- (x + s)(x + t)
--       || 
-- x^2 +(s+t)x + st

-- so we see b = s+t and c = st.  Can we factor by solving equations?
-- How do you pull the coefficients from a polynomial using M2?

R = QQ[b,c,s,t,MonomialOrder => Lex]
I = ideal(b-s-t,c-s*t)
gens gb I

R = QQ[t,s,b,c,MonomialOrder => Lex]
I = ideal(b-s-t,c-s*t)
gens gb I     

---- The second gb is interesting because it is different from the
---- original set of equations. And it helps you solve, as the first
---- generator says that -s is a root of the equation. The second
---- generator gives a relation between s, t, and b.

-- Yes the gb forced -s to be a root, but it is not telling us that t
-- is a root. Think about that. Replace the degree 2 polynomial by a
-- higher degree polynomial, what happens then?

----------------------------------------------------------------------
-- Day 2                                                            --
----------------------------------------------------------------------

-- Last time we were looking at:

R = QQ[x,y, MonomialOrder => Lex]
L = ideal(x^2+y^2 - 1, x*y+y - 5)
transpose gens gb L

-- Why is Lex the best ordering the best to use from this point of
-- view? 

-- Hint: Think Elimination Theorem.

---- Can you repeat the question?

-- We want an equivalent system of equations which involves just one
-- variable--then we can use newton's method to find a solution.

-- Ok the Elimination theorem says that any logical consequence of
-- these equations relying on just one variable will be a consequence
-- of an equation in the gb only relying on one variable.

---- Let L be our ideal, and the subring we are intersecting with is
---- QQ[y], this will just give us the polynomial just in y. The
---- Elimination Theorem says that when we use an elimination
---- ordering, we can just intersect with the gb. Hence if such
---- polynomials exist in the ideal, computing a gb with an
---- elimination ordering (Lex for example) will give the generators
---- of the elements in the desired variable.

-- Yes in our example above, L intersect QQ[y] is generated by 

-- (y^4 - 10y + 25)

---- How do we know such an element exists?

-- If there is a nonzero element of I intersect QQ[y], then there will
-- be one in the gb too.

-- Remember what we were doing was intersecting a circle with a
-- hyperbola. If we look at the code

-- with(plots,implicitplot);
-- implicitplot([x^2+y^2-1,x*y+y-5],x=-5..5,y = -5..5);

-- A heuristic argument: In Maple, we'll see that all the solutions
-- are imaginary. However, suppose the solutions were real. Now
-- project the roots (x,y) -> y this is the projection map.

-- i.e. take this Maple plot:

-- with(plots,implicitplot);
-- implicitplot([x^2+y^2-1,x*y-.2],x=-5..5,y = -5..5);

-- and project onto the y-axis.

-- From the 4 roots in the real case, we see we have 4 points in the
-- projection

-- Any polynomial in I intersect QQ[y] has y_1,y_2,y_3,y_4 as
-- roots. Is there such a polynomial?

---- Yes (y-y_1)(y-y_2)(y-y_3)(y-y_4)

-- We may need some power of the factors - Morally: Elimination is projection.

---- So the gb is computing the projection on to the the y-axis

-- Even more, in Lex, we are projecting on to higher dimensional lines,
-- planes, etc.

---- What is it about Lex ordering that makes the Elimination Theorem
---- work?

-- Good question. What's the answer?

---- In Lex the terms that have x at all are bigger than the terms not
---- containing x, you start breaking them off when doing the projection.

-- Ok I'll give the contrapositive: Suppose you have a monomial
-- involving just y, then any monomial bigger than this monomial also
-- involves just y.

-- The other topic we talked about last time was:

R = QQ[t,s,b,c,MonomialOrder => Lex]
I = ideal(b-s-t,c-s*t)
gens gb I     

-- The two roots given by the quadratic formula add up to a. Now try
-- to do this with 3 variables, 4 variables etc.  It will help to
-- restart M2 at this point.

restart
n = 5
QQ[x,s_1..s_n,a_1..a_n,MonomialOrder => Lex] -- note that the order of the s's and a's is important
f = x^n + sum for i from 1 to n list a_i*x^(n-i) -- variables you want to eliminate should come first
g = product for i from 1 to n list hold (x - s_i)
g = value g
netList transpose entries gens gb ideal (coefficients(f-g,Variables => x))_1

-- When we say find the 5 roots of a polynomial of degree 5, what we
-- really mean is we want the 5 linear factors. Supposing you have a
-- black box that gives you as single root to any polynomial in any
-- degree, how can you get another equation of degree 5?

---- Just divide the linear factor out.

-- OK take f and divide out by (x-s_n)

f % (x-s_n) -- note that this is f(s_n), the last element of the gb
f // (x-s_n) % (x-s_(n-1)) -- Ah! note this is the degree 4 element of the gb
f // (x-s_n) // (x-s_(n-1)) % (x-s_(n-2)) 
f // (x-s_n) // (x-s_(n-1)) // (x-s_(n-2)) % (x-s_(n-3)) 
f // (x-s_n) // (x-s_(n-1)) // (x-s_(n-2)) // (x-s_(n-3)) % (x-s_(n-3)) 
f // (x-s_n) // (x-s_(n-1)) // (x-s_(n-2)) // (x-s_(n-3)) // (x-s_(n-4)) % (x-s_(n-3)) 


-- From this we see that when we divided by successive roots, we get
-- the elements of the gb. By thinking about the above equations, we
-- see that the ideal generated by the gb is the ideal generated by
-- our starting generators. 

-- As a consequence, we have the following theorem on elementary
-- symmetric functions.

-- THM: Any polynomial p(s_1,..,s_n) which is symmetric can be
-- expressed in terms of a_1..a_n where

-- a_1 = s_1 + .. + s_n
-- a_n = s_1*..*s_n

-- Our final experiment involves the following:

-- g(x) = x^m + c_1 x^(m-1) + .. + c_m

-- We want the gb of the equations that say g | f.  These are the
-- coefficients of f % g.

-- Start with n = 4 and m = 2.

n = 4
m = 1
QQ[x,c_1..c_m,a_1..a_n] 
f = x^n + sum for i from 1 to n list a_i*x^(n-i)
g = x^m + sum for i from 1 to m list c_i*x^(m-i)
netList transpose entries gens gb ideal (coefficients(f%g,Variables => x))_1
L41 = netList entries leadTerm gens gb ideal (coefficients(f%g,Variables => x))_1

n = 4
m = 2
QQ[x,c_1..c_m,a_1..a_n] 
f = x^n + sum for i from 1 to n list a_i*x^(n-i)
g = x^m + sum for i from 1 to m list c_i*x^(m-i)
netList transpose entries gens gb ideal (coefficients(f%g,Variables => x))_1
L42 = netList entries leadTerm gens gb ideal (coefficients(f%g,Variables => x))_1

n = 4
m = 3
QQ[x,c_1..c_m,a_1..a_n] 
f = x^n + sum for i from 1 to n list a_i*x^(n-i)
g = x^m + sum for i from 1 to m list c_i*x^(m-i)
netList transpose entries gens gb ideal (coefficients(f%g,Variables => x))_1
L43 = netList entries leadTerm gens gb ideal (coefficients(f%g,Variables => x))_1

n = 4
m = 4
QQ[x,c_1..c_m,a_1..a_n] 
f = x^n + sum for i from 1 to n list a_i*x^(n-i)
g = x^m + sum for i from 1 to m list c_i*x^(m-i)
netList transpose entries gens gb ideal (coefficients(f%g,Variables => x))_1
L44 = netList entries leadTerm gens gb ideal (coefficients(f%g,Variables => x))_1

L41
L42
L43
L44

-- Let's put this together into one function:

L = (n,m)-> (
     QQ[x,c_1..c_m,a_1..a_n]; 
     f := x^n + sum for i from 1 to n list a_i*x^(n-i);
     g := x^m + sum for i from 1 to m list c_i*x^(m-i);
     netList entries leadTerm gens gb ideal (coefficients(f%g,Variables => x))_1
)

L(6,1)
L(6,2)
L(6,3)
L(6,4)
L(6,5)
L(6,6)

-- In conclusion: No matter what you take m and n to be, the lead
-- terms are all monic polynomials of the same degree in fact it is
-- all monomials of degree n - m + 1. 

-- Knowing in advance the form for this ideal helps us compute in what
-- are called "intersection rings" rings which help us count how
-- curves intersect with connections to string theory.

--==================================================================--
-- FINE (we're Italian today)                                       --
--==================================================================--