assignment-1-solution.sagews

find
%html
<h1>
    Assignment 1 - solution
</h1>
<p>
    Some of the solutions are based on your worksheets.
</p>

Assignment 1 - solution

Some of the solutions are based on your worksheets.

Introduction

Define a 2-variate function by $$f(x,y) = x^2+xy-y^2$$ and plot its graph.

x,y=var('x,y');
def f(x,y):
    return x^2 + x*y - y^2
plot3d(f(x,y), (x,-1,1), (y,-1,1))

3D rendering not yet implemented

#this is not working... only in 1D
g(x,y) = x^2*y/cos(x)
g.plot((x,-pi,pi),(y,0,10))

Error in lines 2-2 Traceback (most recent call last): File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "sage/symbolic/expression.pyx", line 10984, in sage.symbolic.expression.Expression.plot (/projects/sage/sage-6.9/src/build/cythonized/sage/symbolic/expression.cpp:58633) f = self._plot_fast_callable(param) File "sage/symbolic/expression.pyx", line 11034, in sage.symbolic.expression.Expression._plot_fast_callable (/projects/sage/sage-6.9/src/build/cythonized/sage/symbolic/expression.cpp:59243) return fast_callable(self, vars=vars, expect_one_var=True) File "sage/ext/fast_callable.pyx", line 456, in sage.ext.fast_callable.fast_callable (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:4278) et = x._fast_callable_(etb) File "sage/symbolic/expression.pyx", line 10879, in sage.symbolic.expression.Expression._fast_callable_ (/projects/sage/sage-6.9/src/build/cythonized/sage/symbolic/expression.cpp:58036) return fast_callable(self, etb) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1570, in fast_callable return FastCallableConverter(ex, etb)() File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 216, in __call__ return self.arithmetic(div, div.operator()) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1498, in arithmetic return reduce(lambda x,y: self.etb.call(operator, x,y), operands) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1498, in <lambda> return reduce(lambda x,y: self.etb.call(operator, x,y), operands) File "sage/ext/fast_callable.pyx", line 734, in sage.ext.fast_callable.ExpressionTreeBuilder.call (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:6627) return ExpressionCall(self, fn, map(self, args)) File "sage/ext/fast_callable.pyx", line 609, in sage.ext.fast_callable.ExpressionTreeBuilder.__call__ (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:5734) return fc(self) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 124, in _fast_callable_ return fast_callable(self, etb) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1570, in fast_callable return FastCallableConverter(ex, etb)() File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 216, in __call__ return self.arithmetic(div, div.operator()) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1498, in arithmetic return reduce(lambda x,y: self.etb.call(operator, x,y), operands) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1498, in <lambda> return reduce(lambda x,y: self.etb.call(operator, x,y), operands) File "sage/ext/fast_callable.pyx", line 734, in sage.ext.fast_callable.ExpressionTreeBuilder.call (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:6627) return ExpressionCall(self, fn, map(self, args)) File "sage/ext/fast_callable.pyx", line 609, in sage.ext.fast_callable.ExpressionTreeBuilder.__call__ (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:5725) return fc(self) File "sage/symbolic/expression.pyx", line 10879, in sage.symbolic.expression.Expression._fast_callable_ (/projects/sage/sage-6.9/src/build/cythonized/sage/symbolic/expression.cpp:58036) return fast_callable(self, etb) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1570, in fast_callable return FastCallableConverter(ex, etb)() File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 211, in __call__ return self.symbol(ex) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py", line 1519, in symbol return self.etb.var(SR(ex)) File "sage/ext/fast_callable.pyx", line 681, in sage.ext.fast_callable.ExpressionTreeBuilder.var (/projects/sage/sage-6.9/src/build/cythonized/sage/ext/fast_callable.c:6227) raise ValueError, "Variable '%s' not found" % var_name ValueError: Variable 'y' not found

Plot a graph of a 1-variate function including a tangent line at a point $x_0$.

def plot_graph_and_tangent_line(f,x0):
    ran = (-3+x0,3+x0)
    g1 = plot(f,ran)
    g2 = plot(f(x0) + f.diff()(x0)*(x-x0), (x,ran[0],ran[1]), color='red')
    show(g1+g2)

# for example...
f(x) = x^2+x-1
plot_graph_and_tangent_line(f, 1)

Find out how to make interactive cells and make an example.

@interact
def _(x0 = input_box( default=0, type = RR, label = "$x_0$:")):
    plot_graph_and_tangent_line(f, x0)

Interact: please open in CoCalc

Test numerically if for $f: \mathbb{N} \to \mathbb{N}$ given by $$f(n) = \begin{cases} 3n+1 \ \ \text{ if } n \text{ is odd} \\ n/2 \ \ \text{ if } n \text{ is even} \end{cases}$$ the following holds (Collatz's conjecture): $\forall n \exists k (f^k(n) = 1 )$. Make a plot of the list of points for a fixed $n$.

def f(n):
    if n % 2 == 0:
        return n/2
    else:
        return 3*n+1

def test_conjecture(start_n, limit=1000):
    j = 0; n = start_n;
    while n != 1 and j < limit:
        n = f(n); j += 1;
    if n != 1:
        print('Limit reached!')
    else:
        print('Test successful, found'),
        print("k = %s" % j)

test_conjecture(100)

Test successful, found k = 25

* Do an interactive plot of a 2-variate function and its tangent plane at a point ($x_0,y_0$) where the point $(x_0,y_0)$ is the input.

reset()
@interact(auto_update=False)
def _(fun_sym = input_box(default='x^2-(y-2)^2+8+x*y', type = str, label = "Function:"),
      x0 = input_box( default=0, type = RR, label = "$x_0$:"),
      y0 = input_box( default=0, type = RR, label = "$y_0$:"),
      r = input_box( default=1,  label = "Range:")
     ):
    fun(x,y)=sage.misc.sage_eval.sage_eval(fun_sym,locals={'y':y, 'x':x})
    dif_fun_x=diff(fun, x)
    #print dif_fun_x
    dif_fun_y=diff(fun, y)
    #print dif_fun_y
    fun_plot=plot3d(fun,(-r,r),(-r,r))

    tangent_plot=plot3d(dif_fun_x(x0,y0)*(x-x0)+dif_fun_y(x0,y0)*(y-y0)+fun(x0,y0), (x,-r,r),(y,-r,r) , color='red')
    show(fun_plot+tangent_plot)

Interact: please open in CoCalc

Write a program listing all cyclic subgroups of $\mathbb{Z}_n^\times$ (modular multiplicative group modulo $n$). * Indicate whether there are also other subgroups or not.

#there are many solutions to this problem: I tried to use the existing methods as much as possible without listing all subgroups
def list_cyclic_subgroups(modulo_n):
    G = IntegerModRing(modulo_n).unit_group()
    A = set()
    for x in G:
        A.add(frozenset(G.submonoid([x.value()]))) #it looks like there is a problem in submonoid...there is always 1 twice...
    if not G.is_cyclic():
        print 'There are also non-cyclic subgroups.' #...G is a non-cyclic subgroup ;-)
    return A


print list_cyclic_subgroups(12)
print list_cyclic_subgroups(15)
print list_cyclic_subgroups(7)

There are also non-cyclic subgroups. set([frozenset([1, 1, 7]), frozenset([1, 1, 5]), frozenset([1, 1, 11]), frozenset([1, 1])]) There are also non-cyclic subgroups. set([frozenset([1, 1, 14]), frozenset([1, 1, 4]), frozenset([1, 1]), frozenset([1, 1, 4, 13, 7]), frozenset([1, 8, 2, 4, 1]), frozenset([1, 8, 2, 4, 1]), frozenset([1, 1, 11]), frozenset([1, 1, 4, 13, 7])]) set([frozenset([1, 1, 2, 4]), frozenset([1, 2, 3, 4, 5, 6, 1]), frozenset([1, 1]), frozenset([1, 1, 2, 4]), frozenset([1, 2, 3, 4, 5, 6, 1]), frozenset([1, 1, 6])])

* Write a program listing all generators of $\mathbb{Z}_n^\times$ (if the group is cyclic).

#the same comment as for the previous task
def list_generators(modulo_n):
    G = IntegerModRing(modulo_n).unit_group()
    if not G.is_cyclic():
        return False
    order = len(G)
    g = G.gen()
    return [y.value() for y in (g^k for k in IntegerModRing(order).list_of_elements_of_multiplicative_group())]

for x in xrange(10,25):
    print list_generators(x)

[7, 3] [2, 8, 7, 6] False [2, 6, 11, 7] [3, 5] False False [3, 10, 5, 11, 14, 7, 12, 6] [11, 5] [2, 13, 14, 15, 3, 10] False False [13, 19, 7, 17] [5, 10, 20, 17, 11, 21, 19, 15, 7, 14] False

Number theory

Find the smallest field which contains $\mathbb{Q}[x]$. See fraction field.

P.<x> = QQ[]
F = P.fraction_field()
F
F.an_element()
1/x in F

Fraction Field of Univariate Polynomial Ring in x over Rational Field x True

* Find a representation of the object of formal power series over $\mathbb{Q}$.

P.<x> = QQ[[]]
P

print P.some_elements()
1/x in P

Power Series Ring in x over Rational Field [x] False

Let $p(x)$ be a polynomial over $K$. Check whether it is irreducible.

reset()
def is_polynomial_irreducible(p):
    try:
        p.parent().polynomials #to test that the parent is a ring of polynomials? (this is not a very good way...)
        return p.is_irreducible() #we could also check that p is a polynomial
    except Exception, e:
        raise ValueError(str(p) + " is not a polynomial.")


K.<t> = NumberField(x^2-2)
x = polygen(K)
p = x^3+x+1
print is_polynomial_irreducible(p)

try:
    print is_polynomial_irreducible(1010)
except Exception, e:
    print e

K.<t> = ZZ[]
print is_polynomial_irreducible(K(1010))

True 1010 is not a polynomial. False

Write a program listing all polynomials of $K[x]$ which are irreducible over $K$ and of degree at most $d$. Include a verification that $K$ is a ring (* throw an exception if not). (* Do not use SageMath's method to check irreducibility.)

#for K infinite, we can consider returning a generator (but it makes little sense)
def list_irreducible_polynomials(K, max_degree):
    """
    Return the list of irreducible polynomials over `K` of degreed less than or equal to `max_degree`. The method works only if `K` is finite.
    """
    try:
        isRing=K.is_ring()
    except Exception, e:
        raise ValueError(str(K) + ' is not a ring: '+ str(e))
    if not isRing:
        raise ValueError(str(K) + ' is not a ring.')
    P.<x> = K[]
    if K.is_finite(): #brute force
        irr=[]
        for d in xrange(1,max_degree+1):
            for p in P.polynomials(d):
                if p.is_irreducible():
                    irr.append(p)
    else:
        raise ValueError(str(K) + '  is not finite.')
    return irr


print list_irreducible_polynomials(IntegerModRing(5),3)
print list_irreducible_polynomials(10,5)

[x, x + 1, x + 2, x + 3, x + 4, 2*x, 2*x + 1, 2*x + 2, 2*x + 3, 2*x + 4, 3*x, 3*x + 1, 3*x + 2, 3*x + 3, 3*x + 4, 4*x, 4*x + 1, 4*x + 2, 4*x + 3, 4*x + 4, x^2 + 2, x^2 + 3, x^2 + x + 1, x^2 + x + 2, x^2 + 2*x + 3, x^2 + 2*x + 4, x^2 + 3*x + 3, x^2 + 3*x + 4, x^2 + 4*x + 1, x^2 + 4*x + 2, 2*x^2 + 1, 2*x^2 + 4, 2*x^2 + x + 1, 2*x^2 + x + 3, 2*x^2 + 2*x + 2, 2*x^2 + 2*x + 4, 2*x^2 + 3*x + 2, 2*x^2 + 3*x + 4, 2*x^2 + 4*x + 1, 2*x^2 + 4*x + 3, 3*x^2 + 1, 3*x^2 + 4, 3*x^2 + x + 2, 3*x^2 + x + 4, 3*x^2 + 2*x + 1, 3*x^2 + 2*x + 3, 3*x^2 + 3*x + 1, 3*x^2 + 3*x + 3, 3*x^2 + 4*x + 2, 3*x^2 + 4*x + 4, 4*x^2 + 2, 4*x^2 + 3, 4*x^2 + x + 3, 4*x^2 + x + 4, 4*x^2 + 2*x + 1, 4*x^2 + 2*x + 2, 4*x^2 + 3*x + 1, 4*x^2 + 3*x + 2, 4*x^2 + 4*x + 3, 4*x^2 + 4*x + 4, x^3 + x + 1, x^3 + x + 4, x^3 + 2*x + 1, x^3 + 2*x + 4, x^3 + 3*x + 2, x^3 + 3*x + 3, x^3 + 4*x + 2, x^3 + 4*x + 3, x^3 + x^2 + 1, x^3 + x^2 + 2, x^3 + x^2 + x + 3, x^3 + x^2 + x + 4, x^3 + x^2 + 3*x + 1, x^3 + x^2 + 3*x + 4, x^3 + x^2 + 4*x + 1, x^3 + x^2 + 4*x + 3, x^3 + 2*x^2 + 1, x^3 + 2*x^2 + 3, x^3 + 2*x^2 + x + 3, x^3 + 2*x^2 + x + 4, x^3 + 2*x^2 + 2*x + 2, x^3 + 2*x^2 + 2*x + 3, x^3 + 2*x^2 + 4*x + 2, x^3 + 2*x^2 + 4*x + 4, x^3 + 3*x^2 + 2, x^3 + 3*x^2 + 4, x^3 + 3*x^2 + x + 1, x^3 + 3*x^2 + x + 2, x^3 + 3*x^2 + 2*x + 2, x^3 + 3*x^2 + 2*x + 3, x^3 + 3*x^2 + 4*x + 1, x^3 + 3*x^2 + 4*x + 3, x^3 + 4*x^2 + 3, x^3 + 4*x^2 + 4, x^3 + 4*x^2 + x + 1, x^3 + 4*x^2 + x + 2, x^3 + 4*x^2 + 3*x + 1, x^3 + 4*x^2 + 3*x + 4, x^3 + 4*x^2 + 4*x + 2, x^3 + 4*x^2 + 4*x + 4, 2*x^3 + x + 1, 2*x^3 + x + 4, 2*x^3 + 2*x + 2, 2*x^3 + 2*x + 3, 2*x^3 + 3*x + 1, 2*x^3 + 3*x + 4, 2*x^3 + 4*x + 2, 2*x^3 + 4*x + 3, 2*x^3 + x^2 + 3, 2*x^3 + x^2 + 4, 2*x^3 + x^2 + 2*x + 2, 2*x^3 + x^2 + 2*x + 4, 2*x^3 + x^2 + 3*x + 1, 2*x^3 + x^2 + 3*x + 2, 2*x^3 + x^2 + 4*x + 1, 2*x^3 + x^2 + 4*x + 4, 2*x^3 + 2*x^2 + 2, 2*x^3 + 2*x^2 + 4, 2*x^3 + 2*x^2 + x + 2, 2*x^3 + 2*x^2 + x + 3, 2*x^3 + 2*x^2 + 2*x + 1, 2*x^3 + 2*x^2 + 2*x + 3, 2*x^3 + 2*x^2 + 3*x + 1, 2*x^3 + 2*x^2 + 3*x + 2, 2*x^3 + 3*x^2 + 1, 2*x^3 + 3*x^2 + 3, 2*x^3 + 3*x^2 + x + 2, 2*x^3 + 3*x^2 + x + 3, 2*x^3 + 3*x^2 + 2*x + 2, 2*x^3 + 3*x^2 + 2*x + 4, 2*x^3 + 3*x^2 + 3*x + 3, 2*x^3 + 3*x^2 + 3*x + 4, 2*x^3 + 4*x^2 + 1, 2*x^3 + 4*x^2 + 2, 2*x^3 + 4*x^2 + 2*x + 1, 2*x^3 + 4*x^2 + 2*x + 3, 2*x^3 + 4*x^2 + 3*x + 3, 2*x^3 + 4*x^2 + 3*x + 4, 2*x^3 + 4*x^2 + 4*x + 1, 2*x^3 + 4*x^2 + 4*x + 4, 3*x^3 + x + 2, 3*x^3 + x + 3, 3*x^3 + 2*x + 1, 3*x^3 + 2*x + 4, 3*x^3 + 3*x + 2, 3*x^3 + 3*x + 3, 3*x^3 + 4*x + 1, 3*x^3 + 4*x + 4, 3*x^3 + x^2 + 3, 3*x^3 + x^2 + 4, 3*x^3 + x^2 + x + 1, 3*x^3 + x^2 + x + 4, 3*x^3 + x^2 + 2*x + 1, 3*x^3 + x^2 + 2*x + 2, 3*x^3 + x^2 + 3*x + 2, 3*x^3 + x^2 + 3*x + 4, 3*x^3 + 2*x^2 + 2, 3*x^3 + 2*x^2 + 4, 3*x^3 + 2*x^2 + 2*x + 1, 3*x^3 + 2*x^2 + 2*x + 2, 3*x^3 + 2*x^2 + 3*x + 1, 3*x^3 + 2*x^2 + 3*x + 3, 3*x^3 + 2*x^2 + 4*x + 2, 3*x^3 + 2*x^2 + 4*x + 3, 3*x^3 + 3*x^2 + 1, 3*x^3 + 3*x^2 + 3, 3*x^3 + 3*x^2 + 2*x + 3, 3*x^3 + 3*x^2 + 2*x + 4, 3*x^3 + 3*x^2 + 3*x + 2, 3*x^3 + 3*x^2 + 3*x + 4, 3*x^3 + 3*x^2 + 4*x + 2, 3*x^3 + 3*x^2 + 4*x + 3, 3*x^3 + 4*x^2 + 1, 3*x^3 + 4*x^2 + 2, 3*x^3 + 4*x^2 + x + 1, 3*x^3 + 4*x^2 + x + 4, 3*x^3 + 4*x^2 + 2*x + 3, 3*x^3 + 4*x^2 + 2*x + 4, 3*x^3 + 4*x^2 + 3*x + 1, 3*x^3 + 4*x^2 + 3*x + 3, 4*x^3 + x + 2, 4*x^3 + x + 3, 4*x^3 + 2*x + 2, 4*x^3 + 2*x + 3, 4*x^3 + 3*x + 1, 4*x^3 + 3*x + 4, 4*x^3 + 4*x + 1, 4*x^3 + 4*x + 4, 4*x^3 + x^2 + 1, 4*x^3 + x^2 + 2, 4*x^3 + x^2 + x + 1, 4*x^3 + x^2 + x + 3, 4*x^3 + x^2 + 2*x + 1, 4*x^3 + x^2 + 2*x + 4, 4*x^3 + x^2 + 4*x + 3, 4*x^3 + x^2 + 4*x + 4, 4*x^3 + 2*x^2 + 1, 4*x^3 + 2*x^2 + 3, 4*x^3 + 2*x^2 + x + 2, 4*x^3 + 2*x^2 + x + 4, 4*x^3 + 2*x^2 + 3*x + 2, 4*x^3 + 2*x^2 + 3*x + 3, 4*x^3 + 2*x^2 + 4*x + 3, 4*x^3 + 2*x^2 + 4*x + 4, 4*x^3 + 3*x^2 + 2, 4*x^3 + 3*x^2 + 4, 4*x^3 + 3*x^2 + x + 1, 4*x^3 + 3*x^2 + x + 3, 4*x^3 + 3*x^2 + 3*x + 2, 4*x^3 + 3*x^2 + 3*x + 3, 4*x^3 + 3*x^2 + 4*x + 1, 4*x^3 + 3*x^2 + 4*x + 2, 4*x^3 + 4*x^2 + 3, 4*x^3 + 4*x^2 + 4, 4*x^3 + 4*x^2 + x + 2, 4*x^3 + 4*x^2 + x + 4, 4*x^3 + 4*x^2 + 2*x + 1, 4*x^3 + 4*x^2 + 2*x + 4, 4*x^3 + 4*x^2 + 4*x + 1, 4*x^3 + 4*x^2 + 4*x + 2]

Error in lines 21-21 Traceback (most recent call last): File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 8, in list_irreducible_polynomials ValueError: 10 is not a ring: 'sage.rings.integer.Integer' object has no attribute 'is_ring'

%html
Let $K$ be a field and $\alpha$ and $\beta$ be two algebraic numbers over $K$. Let $f \in K[x,y]$ be a two-variate polynomial over $K$. Write a function that outputs the degree of $f(\alpha, \beta)$ (over $K$) with $\alpha$ and $\beta$ being two inputs.

Let $K$ be a field and $\alpha$ and $\beta$ be two algebraic numbers over $K$. Let $f \in K[x,y]$ be a two-variate polynomial over $K$. Write a function that outputs the degree of $f(\alpha, \beta)$ (over $K$) with $\alpha$ and $\beta$ being two inputs.

reset()
def find_degree(poly,alpha,beta):
    #alpha and beta are required to have a coercion to CC specified !
    #not (yet?) working on finite fields

    epsilon = 10^(-5) #the epsilon to check zero - will cause bugs when poly contains a lot of operations

    #K = alpha.parent().base_field() #for finite fields, this is not working :-)
    K = alpha.parent().base_ring() #but this will return the ambient field :-)
    k = K.gen()

    if K != beta.parent().base_ring():
        raise ValueError("The base field of alpha and beta need to be the same.")

    #let's find the minimal polynomial of beta over A
    for (fa,_) in beta.absolute_minpoly().base_extend(A).factor(): #one of the factors is our minimal polynomila
        if abs(fa.base_extend(CC)(beta)) < epsilon: #we shall check its value
            minpoly = fa #this is my minpoly
            break

    #now we can find the field K(alpha,beta)
    E.<beta1> = A.extension(minpoly,latex_name='beta') # latex name is not working...
    #and let's find the right embedding to CC
    for em in E.complex_embeddings():
        if abs(em(k) - CC(k))<epsilon and abs(CC(alpha) - em(alpha)) < epsilon and abs(CC(beta)-em(beta1))<epsilon:
            break #I have my embedding

    #... and calculate in it the value of poly(alpha,beta)
    z = poly(alpha,beta1)

    #let's find the minimal polynomial of z=poly(alpha,beta) over K
    print 'We are looking for the minimal polynomial of ',
    show(z,display=false)
    print 'over ',
    print K
    for (fa,_) in z.absolute_minpoly().base_extend(K).factor(): #one of the factors is our minimal polynomial
        if abs(fa(em(z))) < epsilon: #we shall check its value :-(
            print 'Winner is ',
            print fa,
            print 'having degree',
            print fa.degree()

    return fa.degree()

t = polygen(QQ)
K.<k> = NumberField(t^2-3,embedding=1)
q = polygen(K)
def f(x,y): return x+y^3*x
A.<alpha> = NumberField(q^2-5)
alpha_embedding = A.complex_embeddings()[0]
B.<beta> = NumberField(q^4-7+k)
beta_embedding = B.complex_embeddings()[0]

CC._unset_coercions_used()
CC.register_coercion(beta_embedding)
CC.register_coercion(alpha_embedding)


alpha_embedding(alpha) == CC(alpha)
beta_embedding(beta) == CC(beta)
#beta_embedding(beta)
#CC(beta) #not working, why? (well, it did not work)
show(k)
show(alpha)
find_degree(f,alpha,beta)

True True

$\displaystyle k$

$\displaystyle \alpha$

We are looking for the minimal polynomial of

$\alpha \beta_{1}^{3} + \alpha$

over Number Field in k with defining polynomial x^2 - 3 Winner is x^8 - 20*x^6 + (-7500*k - 20150)*x^4 + (-225000*k - 609500)*x^2 + 75937500*k + 144703125 having degree 8 8

t = polygen(QQ)
A.<alpha> = NumberField(t^2-2,embedding=1)
B.<beta> = NumberField(t^4-2,embedding=1)

find_degree(f,alpha,beta)

We are looking for the minimal polynomial of

$2 \beta_{1} + \alpha$

over Rational Field Winner is x^4 - 4*x^2 - 32*x - 28 having degree 4 4

t = polygen(QQ)
A.<alpha> = NumberField(t^2-2,embedding=1)
B.<beta> = NumberField(t^2-2,embedding=1)

find_degree(f,alpha,beta)

We are looking for the minimal polynomial of

$\alpha + 4$

over Rational Field Winner is x^2 - 8*x + 14 having degree 2 2

F.<ff> = GF(3)
x = polygen(F)
A.<a> = F.extension(x^2+x+1,'a')
B.<b> = F.extension(x^3+x+1,'b')
#F.extension?
#A.<alpha> = NumberField(t^2-2,embedding=1)
#B.<beta> = NumberField(t^2-2,embedding=1)

a.base_ring()

find_degree(f,a,b)

Finite Field of size 3

Error in lines 9-9 Traceback (most recent call last): File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/rings/complex_field.py", line 351, in __call__ return Parent.__call__(self, x) File "sage/structure/parent.pyx", line 1097, in sage.structure.parent.Parent.__call__ (/projects/sage/sage-6.9/src/build/cythonized/sage/structure/parent.c:9873) return mor._call_(x) File "sage/structure/coerce_maps.pyx", line 109, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/projects/sage/sage-6.9/src/build/cythonized/sage/structure/coerce_maps.c:4539) raise File "sage/structure/coerce_maps.pyx", line 104, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/projects/sage/sage-6.9/src/build/cythonized/sage/structure/coerce_maps.c:4432) return C._element_constructor(x) File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/sage/rings/complex_field.py", line 393, in _element_constructor_ return complex_number.ComplexNumber(self, x) File "sage/rings/complex_number.pyx", line 188, in sage.rings.complex_number.ComplexNumber.__init__ (/projects/sage/sage-6.9/src/build/cythonized/sage/rings/complex_number.c:4283) raise TypeError, "unable to coerce to a ComplexNumber: %s" % type(real) TypeError: unable to coerce to a ComplexNumber: <class 'sage.rings.polynomial.polynomial_quotient_ring_element.PolynomialQuotientRing_generic_with_category.element_class'>

* Write a function that given an input $x$ it computes the continued fraction of $x$. The return value must be iterable - i.e., a generator. Hint: see yield statement. Compare with the output of SageMath continued_fraction function.

def continuedFraction(x):
    #not very sophisticated test
    try:
        if x not in QQ:
            x = RealField(200)(x) #we will approximate...
        else:
            x = QQ(x)
    except ValueError, e:
        raise ValueError('x must be a real number')
    try:
        while True:
            coef = floor(x)
            yield coef
            x = 1/(x-coef)
    except ZeroDivisionError, e:
        pass #we are finished
    except Exception, e:
        pass #floor may throw some other exception

#this will work fine
list(continuedFraction(2))
list(continuedFraction(5/342))

#this will fail (but it will run perfectly fine (and far)) (don't run it)
#list(continuedFraction(sqrt(2)))

#to print only first few members of an iterator, we can use the following
N = 25
import itertools
list(itertools.islice(continuedFraction(2/342341), 0, N))
list(itertools.islice(continuedFraction(sqrt(2)), 0, N))


#continuedFraction(2)[:100]

[2] [0, 68, 2, 2] [0, 171170, 2] [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

* Given a finite field, write a program that finds its normal basis, i.e., a basis of the form $(a, a^p, \ldots, a^{p^n})$ whith $p^n$ being the order of the field.

#there is a mistake in the task, the last vector shoul be a^(p^(n-1))
#without any other knowledge, let's do a brute force search....
def find_normal_basis(order_of_field):

    F.<g> = FiniteField(order_of_field)
    p = F.characteristic()
    pe = F.primitive_element()
    V = F.vector_space()
    n = V.dimension()

    current = pe
    for i in xrange(order_of_field):
        if len(V.linear_dependence([V(current^(p^j)) for j in xrange(n)])) == 0:
            print 'A normal element is ',
            print current
            return [current^(p^j) for j in xrange(n)]
        current *= pe

order_of_field = 2^4
find_normal_basis(order_of_field)

A normal element is g^3 [g^3, g^3 + g^2, g^3 + g^2 + g + 1, g^3 + g]

Set $$f(x,y) = 333.75y^6 + x^2 \left(11x^2y^2-y^6-121y^4-2\right)+5.5y^8+\frac{x}{2y}.$$ Evaluate $f(77617,33096)$ using floating point numbers with given $b$ bits of precision. Compare with the exact result.

def f(x,y):
    return 33375/100 *y^6 + x^2 *(11*x^2*y^2 - y^6 - 121*y^4 - 2) + 55/10*y^8 + x/(2*y)

print 'exact result is ',
f(77617,33096)
print 'which is approximately',
approx = RR(f(77617,33096))
print approx
print ''
print 'bits : results : error'
for i in xrange(20,150):
    print i,
    print ' : ',
    R = RealField(i)
    z = f(R(77617),(33096))
    print z,
    print ' : ',
    print abs(approx-z)

exact result is -54767/66192 which is approximately -0.827396059946821 bits : results : error 20 : -1.0141e31 : 1.0141e31 21 : 5.07060e30 : 5.07060e30 22 : 1.17260 : 2.00000 23 : 1.17260 : 2.00000 24 : -6.33825e29 : 6.33825e29 25 : 1.172604 : 2.000000 26 : 1.172604 : 2.000000 27 : 1.172604 : 2.000000 28 : -3.9614081e28 : 3.9614081e28 29 : 1.9807041e28 : 1.9807041e28 30 : -9.9035203e27 : 9.9035203e27 31 : 1.17260394 : 2.00000000 32 : 2.47588008e27 : 2.47588008e27 33 : -1.23794004e27 : 1.23794004e27 34 : 1.23794004e27 : 1.23794004e27 35 : -3.094850098e26 : 3.094850098e26 36 : 1.172603940 : 2.000000000 37 : -7.737125246e25 : 7.737125246e25 38 : 7.7371252455e25 : 7.7371252455e25 39 : -1.9342813114e25 : 1.9342813114e25 40 : 1.1726039401 : 2.0000000000 41 : 1.17260394005 : 2.00000000000 42 : 1.17260394005 : 2.00000000000 43 : 1.17260394005 : 2.00000000000 44 : -6.04462909807e23 : 6.04462909807e23 45 : -3.022314549037e23 : 3.022314549037e23 46 : 1.172603940053 : 2.000000000000 47 : 7.555786372591e22 : 7.555786372591e22 48 : 1.1726039400532 : 2.0000000000000 49 : 1.8889465931479e22 : 1.8889465931479e22 50 : -1.8889465931479e22 : 1.8889465931479e22 51 : 1.17260394005318 : 2.00000000000000 52 : 2.36118324143482e21 : 2.36118324143482e21 53 : -2.36118324143482e21 : 2.36118324143482e21 54 : 5.90295810358706e20 : 5.90295810358706e20 55 : 1.172603940053179 : 2.00000000000000 56 : 1.172603940053179 : 2.00000000000000 57 : 1.172603940053179 : 2.00000000000000 58 : 3.6893488147419103e19 : 3.68934881474191e19 59 : 1.1726039400531786 : 2.00000000000000 60 : -1.8446744073709552e19 : 1.84467440737096e19 61 : 4.61168601842738790e18 : 4.61168601842739e18 62 : -2.30584300921369395e18 : 2.30584300921369e18 63 : 1.15292150460684698e18 : 1.15292150460685e18 64 : 5.76460752303423489e17 : 5.76460752303423e17 65 : 1.172603940053178632 : 2.00000000000000 66 : 1.441151880758558732e17 : 1.44115188075856e17 67 : -7.205759403792793483e16 : 7.20575940379279e16 68 : -3.6028797018963966827e16 : 3.60287970189640e16 69 : 1.8014398509481985173e16 : 1.80143985094820e16 70 : 1.1726039400531786319 : 2.00000000000000 71 : -4.50359962737049482740e15 : 4.50359962737049e15 72 : 2.25179981368524917260e15 : 2.25179981368525e15 73 : 1.12589990684262517260e15 : 1.12589990684263e15 74 : -5.62949953421310827396e14 : 5.62949953421310e14 75 : -2.814749767106548273961e14 : 2.81474976710654e14 76 : 1.407374883553291726039e14 : 1.40737488355330e14 77 : 1.172603940053178631859 : 2.00000000000000 78 : -3.5184372088830827396060e13 : 3.51843720888300e13 79 : 1.1726039400531786318588 : 2.00000000000000 80 : 1.1726039400531786318588 : 2.00000000000000 81 : 4.39804651110517260394005e12 : 4.39804651110600e12 82 : -2.19902325555082739605995e12 : 2.19902325555000e12 83 : 1.17260394005317863185883 : 2.00000000000000 84 : 5.49755813889172603940053e11 : 5.49755813890000e11 85 : 2.748779069451726039400532e11 : 2.74877906946000e11 86 : 1.172603940053178631858835 : 2.00000000000000 87 : 1.172603940053178631858835 : 2.00000000000000 88 : 1.1726039400531786318588349 : 2.00000000000000 89 : 1.1726039400531786318588349 : 2.00000000000000 90 : 8.5899345931726039400531786e9 : 8.58993459400000e9 91 : -4.29496729482739605994682137e9 : 4.29496729400000e9 92 : 1.17260394005317863185883490 : 2.00000000000000 93 : 1.07374182517260394005317863e9 : 1.07374182600000e9 94 : 1.17260394005317863185883490 : 2.00000000000000 95 : -2.684354548273960599468213681e8 : 2.68435454000000e8 96 : 1.342177291726039400531786319e8 : 1.34217730000000e8 97 : -6.710886282739605994682136814e7 : 6.71088620000000e7 98 : 3.3554433172603940053178631859e7 : 3.35544340000000e7 99 : 1.1726039400531786318588349045 : 2.00000000000000 100 : 1.1726039400531786318588349045 : 2.00000000000000 101 : 1.17260394005317863185883490452 : 2.00000000000000 102 : 1.17260394005317863185883490452 : 2.00000000000000 103 : 1.17260394005317863185883490452 : 2.00000000000000 104 : 1.172603940053178631858834904520 : 2.00000000000000 105 : 1.172603940053178631858834904520 : 2.00000000000000 106 : 1.172603940053178631858834904520 : 2.00000000000000 107 : 1.172603940053178631858834904520 : 2.00000000000000 108 : 1.1726039400531786318588349045202 : 2.00000000000000 109 : 1.1726039400531786318588349045202 : 2.00000000000000 110 : 1.1726039400531786318588349045202 : 2.00000000000000 111 : 1.17260394005317863185883490452018 : 2.00000000000000 112 : 1.17260394005317863185883490452018 : 2.00000000000000 113 : 1.17260394005317863185883490452018 : 2.00000000000000 114 : 1.172603940053178631858834904520184 : 2.00000000000000 115 : 1.172603940053178631858834904520184 : 2.00000000000000 116 : 1.172603940053178631858834904520184 : 2.00000000000000 117 : 1.172603940053178631858834904520184 : 2.00000000000000 118 : 1.1726039400531786318588349045201837 : 2.00000000000000 119 : 1.1726039400531786318588349045201837 : 2.00000000000000 120 : 1.1726039400531786318588349045201837 : 2.00000000000000 121 : 1.17260394005317863185883490452018371 : 2.00000000000000 122 : -0.827396059946821368141165095479816292 : 0.000000000000000 123 : -0.827396059946821368141165095479816292 : 0.000000000000000 124 : -0.8273960599468213681411650954798162920 : 0.000000000000000 125 : -0.8273960599468213681411650954798162920 : 0.000000000000000 126 : -0.8273960599468213681411650954798162920 : 0.000000000000000 127 : -0.8273960599468213681411650954798162920 : 0.000000000000000 128 : -0.82739605994682136814116509547981629200 : 0.000000000000000 129 : -0.82739605994682136814116509547981629200 : 0.000000000000000 130 : -0.82739605994682136814116509547981629200 : 0.000000000000000 131 : -0.827396059946821368141165095479816291999 : 0.000000000000000 132 : -0.827396059946821368141165095479816291999 : 0.000000000000000 133 : -0.827396059946821368141165095479816291999 : 0.000000000000000 134 : -0.8273960599468213681411650954798162919991 : 0.000000000000000 135 : -0.8273960599468213681411650954798162919990 : 0.000000000000000 136 : -0.8273960599468213681411650954798162919990 : 0.000000000000000 137 : -0.8273960599468213681411650954798162919990 : 0.000000000000000 138 : -0.82739605994682136814116509547981629199903 : 0.000000000000000 139 : -0.82739605994682136814116509547981629199903 : 0.000000000000000 140 : -0.82739605994682136814116509547981629199903 : 0.000000000000000 141 : -0.827396059946821368141165095479816291999033 : 0.000000000000000 142 : -0.827396059946821368141165095479816291999033 : 0.000000000000000 143 : -0.827396059946821368141165095479816291999033 : 0.000000000000000 144 : -0.8273960599468213681411650954798162919990332 : 0.000000000000000 145 : -0.8273960599468213681411650954798162919990331 : 0.000000000000000 146 : -0.8273960599468213681411650954798162919990331 : 0.000000000000000 147 : -0.8273960599468213681411650954798162919990331 : 0.000000000000000 148 : -0.82739605994682136814116509547981629199903312 : 0.000000000000000 149 : -0.82739605994682136814116509547981629199903312 : 0.000000000000000

# solution to the following exercices will be provided later

Construct an object representing the lattice $\Lambda = \{ \alpha \cdot 2 + \beta \cdot \omega \colon \alpha, \beta \in \ZZ \}$ where $\omega = {\rm e}^{\frac{2\pi}{3} {\rm i}}$ and the points are understood as points in $\mathbb{R}^2$.

omega =
Lambda =

%html
Find an example of a linear mapping $M: \Lambda \to \Lambda$ such that all eigenvalues of $M$ are greater than $1$ in modulus (such a matrix is called <em>expanding</em>) and such that $\det(I-M) \neq \pm 1$.

Find an example of a linear mapping $M: \Lambda \to \Lambda$ such that all eigenvalues of $M$ are greater than $1$ in modulus (such a matrix is called expanding) and such that $\det(I-M) \neq \pm 1$.

M =

Plot a portion of $\Lambda$ and $M\Lambda$ in one image distinguishing the two sets by colors.

Calculate the number of elements of $\Lambda/M\Lambda$.

Find a set $D$ such that every class of $\Lambda/M\Lambda$ has exactly one representative in $D$.

D =

Define the mapping $\Psi: \Lambda \to \Lambda$ which is given by $$\Psi(x) = M^{-1}(x-d)$$ where $d \in D$ is the unique element such that $x \equiv d \pmod M$, i.e., $x-d \in M\Lambda$.

Psi =

Pick a random (really!) element $x \in \Lambda$ and build a few members of the sequence $x, \Psi(x), \Psi^2(x) \ldots$. Can you observe something?

gcd(0,0)

0

︠7a7bb223-3c89-4f47-bc94-df3e87cff707︠