jump to navigation

Algorithmacs: Algorithmic for Texmacs December 21, 2012

Posted by bossudenotredame in Uncategorized.
add a comment

I have to write down lots of algorithms in my thesis. And I dead decided from day one to use Texmacs over tex+emacs. And don’t try to prove me wrong it’s much faster and more intuitive and it is not MathEdit (what do they even use in MS-Office these days?). The draw back is that lots of stuff aren’t written there for Texmacs including the algorithmic environment and I don’t mean the menu filler joke one there (well other solution is that you can write in Tex and collage it in Texmacs but there is a limit for dirty work.) I found somebody’s half way effort to write one on a mailing list and spent a day or so to make it able to reproduce all CLRS algorithms. It’s not the most intelligent piece of software but it makes sure your algorithms are clean and uniform:


I hope it helps some other person with their algorithms as well and save them that day. And if you improved it, be nice! there’s a button called “merge request”.


Abelian subgroups with a normal cyclic decomposition December 11, 2012

Posted by bossudenotredame in Automorphism Group, Automorphisms of curves, Function fields, Galois Theory.
add a comment

And I’m not that dumb, I mean normal in the bigger group. This strange criteria becomes the only way I can construct some of these coverings for the attack. I wish I could get rid of this strange condition but for now I can’t think of an alternative algorithm. Maybe my brain is rotting.

Just to make the problem interesting I have seen C_3\times C_3 with a non-normal decomposition and at the same time in the same group and same subgroup with the normal decomposition.

But beside having this condition, exhausting the possibility that a group has one of these subgroup (with the fixed field of the Abelian subgroup being rational otherwise $latex  (e)$ would have done it) is another problem.

The golden key is that if it’s normal then this is not the problem. suppose C_i is a part of a decomposition and normal. then if in a new decomposition

C_i \subset eq D_1x...xD_n and C_i is empty. C_i, it should be that C_i \times D_1x...xD_n/C_i so gcg^{-1}gdg^{-1} and because the first part is normal the second part have to be, otherwise will be traped in C_i and contradiction.

This opens the way for a greedy algorithm. If you take off a normal part you are not going to harm the problem, so let take the biggest cyclic part that we can.

Finite fields are so nice! November 19, 2012

Posted by bossudenotredame in Computer Algebra, Galois Theory, Programming, Uncategorized.
add a comment

Well I know I should have known this when I took my undergrad algebra II, but the reality is that finite fields still surprise me with their niceness. Till today. I was trying to basically to add i and \sqrt{3} to a finite field and Sage was giving me a weir look by giving me weird object:

Univariate Quotient Polynomial Ring in y over Univariate Quotient Polynomial Ring in x over Finite Field of size 17 with modulus x^2 + x + 1 with modulus y^2 + 2*y + 1

In my defence, I knew that all degree extension of a prime field are isomorphic but this doesn’t mean that all quadratic polynomial over the prime fields gets their root in a random degree 2 extension automatically. So I wrote this:

P = 31
m = 2
F.<a> = FiniteField(P^m)
R.<x> = PolynomialRing(FiniteField(P))
Rext.<x> = F['x']
for cur_poly in R.monics(of_degree = 2):
    if (Rext(cur_poly).is_irreducible()):
        print "You are wrong :DDDDDDD:", Rext(cur_poly).factor()

print "That's it"

This is because both i, \sqrt{3} are roots of x^{p^2}-x and because this polynomial factors completely the minimal polynomial of those should factor as well.

When python’s dynamism can’t catch to C++ polymorphism November 1, 2012

Posted by bossudenotredame in Computer Algebra, Programming.
add a comment

When you start programming with python, you start pooh-poohing every ritual you had to go through in c++ world. I mean who on the earth in the age of youtube generation wastes its time and break its head dealing with memory allocation, allocating memory is like washing your clothes by hand, when there is a washing machine at arm reach.

However, while writing a code today I missed something I was taking in c++ for granted: function polymorphism is very essential when you inherit objects.

Here, I’m inheriting AutomophismGroup from PermutationGroup in sage. PermutationGroup can generate subgroup using different data, like generators or a gap group. However, AutomorphismGroup need a very specific data (the algebraic equations of the automorphism) to generate a subgroup of AutomorphismGroup kind. On the other hand, the less sophisticated perm subgroups are still legit subgroup of AutomorphismGroup, mathematically speaking.

Now if sage was in c++, this was a none-issue. c++ check how you want to generate the subgroup: with sophisticated data? then it calls the child subgroup function, with primitive data then calls the subgroup function of the parent.

However, sage is in python, and I have to deal with this ugly error cause I have no organic way of preferring parent method over the child.

Morale: Dynamism with all simplicity it has to offer, can’t claim all what typed polymorphism can do.

Get the Automorphism group, spit out the curve equation. September 2, 2012

Posted by bossudenotredame in Automorphism Group.
add a comment

I’m writing a program in Sage, that take an Automorphism group, and “tries” to spit out the curve equation. At this stage I only use “Über die Automorphismengruppen von algebraischen Funktionenkörpern” results. This means that I look at the centre of the Automorphism group G and check if I can write G as an extension of one of a cyclic subgroup of the centre. If I find such a cyclic subgroup then I’m the winner.

This For now, but I might make it more sophisticated later. This is good for my PhD and this is also good for the whole world. I think we lack such a tools.

Insiding out of a sphere September 2, 2012

Posted by bossudenotredame in Fun, Uncategorized.
add a comment

It seems to me that thousands of people were working to make you understand how to take a sphere inside out:


I found it very insightful on how really we do math. It is also fun.

Fixed Field Computation: Magma vs PARI January 8, 2012

Posted by bossudenotredame in Function fields, Galois Theory, Magma.
add a comment

This is how Magma computes the fixed field of a subgroup U of the Galois group of a number field K:

to_field := function(K, U:Partial := false)
if Type(K) eq FldCyc and Type(U) eq GrpAb then
G, Map:= CyclotomicAutomorphismGroup(K);
mG, G := CosetAction(G, sub);
U := U@mG;
Map := Inverse(mG) * Map;
G,_, Map:= AutomorphismGroup(K:Partial := Partial);
end if;
pe := PrimitiveElement(K);
if not IsSimple(K) then
f, GG := CosetAction(G, sub);
Map := Inverse(f)*Map;
G := GG;
U := f(U);
end if;
assert IsTransitive(G);
rt := [pe@(g@Map) where _, g := IsConjugate(G, 1, i) : i in [1..#G]];
if G eq U then
i := SLPolynomialRing(Integers(), Degree(G));
i := &+ [i.j : j in [1..Degree(G)]];
i := RelativeInvariant(G, U);
end if;
t := Polynomial([0,1]);
all_t := {t};
a,b := GetSeed();
r := { Evaluate(i,
[Evaluate(t, x) : x in PermuteSequence(rt, u)]) :
u in Transversal(G, U)};
t := Polynomial([Random(2) : x in all_t] cat [1]);
until t notin all_t;
Include(~all_t, t);
until #r eq #G div #U;
f := &*[Polynomial([-s, 1]) : s in r];
if #G eq Degree(K) then
f := Polynomial(BaseField(K), f);
c := sub;
f := Polynomial(c, f);
end if;
if not exists(x){x : x in r | sub eq U} then
error "cannot find correct embedding";
end if;
k := NumberField(f:Check := false);
Embed(k, K, x);
if #G ne Degree(K) then
k := AbsoluteField(k);
Embed(k, K, K!k.1);
end if;
return k;
end function;

And this is how PARI does it:

galoisfixedfield(GEN gal, GEN perm, long flag, long y)
pari_sp lbot, ltop = avma;
GEN T, L, P, S, PL, O, res, mod, mod2;
long x, n, i;
if (flag2) pari_err(flagerr, "galoisfixedfield");
gal = checkgal(gal); T = gal_get_pol(gal);
x = varn(T);
L = gal_get_roots(gal); n = lg(L)-1;
mod = gal_get_mod(gal);
if (typ(perm) == t_VEC)
if (is_group(perm)) perm = gel(perm, 1);
for (i = 1; i val)
fprintferr("GaloisConj:increase p-adic prec by %ld.\n", Pgb.valabs-val);
PL = ZpX_liftroots(P, PL, Pgb.l, Pgb.valabs);
L = ZpX_liftroots(T, L, Pgb.l, Pgb.valabs);
mod = Pgb.ladicabs;
PM = vandermondeinversemod(PL, P, Pden, mod);
if (y < 0) y = fetch_user_var("y");
if (y <= x)
pari_err(talker,"variable priority too high in galoisfixedfield");
lbot = avma; res = cgetg(4, t_VEC);
gel(res,3) = fixedfieldfactor(L,O,gal_get_group(gal), PM,Pden,mod,mod2,x,y);
gel(res,1) = gcopy(P);
gel(res,2) = gmodulo(S, T);
return gerepile(ltop, lbot, res);

Dihedral vs Dicyclic December 23, 2011

Posted by bossudenotredame in Uncategorized.
add a comment

First, group theory is hard! From far it is easy. When you try to really work with Group and not just look at those nice theorem, your brain halt completely. I mean it is very hard to understand a group the way we understand abelian groups. Without, the fundamental decomposition, my brain even doesn’t know what’s the understanding of a group, let a lone to understand it.

So, I had a group of order 12, non-abelian and I know that’s not A4. So the only possibility is that G is either dihedral or dicyclic. Now I have the group and I need to distinguish them. For now the easiest way I think is the number of order 4, elements. which exists in dicyclic but not in dihedral. Basically the exponent of the group will reveal the story. But does it mean that I understood the dicyclic action, I don’t know. And even if, how should I understand all other groups out there.


Computing the Genus December 12, 2011

Posted by bossudenotredame in Uncategorized.
add a comment

I’m all happy with all abilities that sage gives me to implement my algorithm except for computing Genus. Basically, sage is doing all algebraic geometry but when it’s time to arithmetic geometry, the sage start to linger (or better to say that it offer nothing).

But, at this point all I need is just to compute the Genus of a function field. I know Magma can do it but in following few days I’m going to implement that for Sage and write here about my challenges.

Math is an Art not a Science October 5, 2011

Posted by bossudenotredame in Uncategorized.
1 comment so far

This manifesto is very true:


In my case it was even worse. It wasn’t only the algorithm that we had to memorize. We were forced to memorize some odd factorization of polynomials of high degree that without memorization no one could derive them on the exam.

So till the last year of high school, I liked computer science over Math. This was only because computer science didn’t have a set curriculum and we were free to choose our own problems and the come up with our own algorithm to solve it. (soon Computer Science will be the victim of the same process).

It was the discrete math with graph theory problems that showed me actually math is more than taking derivate of hundreds of functions in single day. Again thanks to the fact that the education system did not have enough time to exhaust and formulate graph theory as it had done it with Calculus and Algebra.