Primitive root mod p

Transire suum pectus mundoque potiri

Thesis Database and Python CGI uploading. 28 January, 2008

Filed under: Programming — Nikolas Karalis @ 6:39 pm

Before a few days I had the idea that it would be really nice if we could have a database of greek theses and dissertations, about mathematics and science in general. From what i know, there are a few databases around, mostly for Electrical Engineering and Computer Science dissertations. So, I thought that it would be a good opportunity for me to exercise my CGI and Python Web scripting skills.

And here I am, presenting the Thesis Database project. I hope that it will be useful and people will contribute.

But while coding the CGI backbone, I had a few problems to solve, so since i had to come up with the solutions (couldn’t find anything useful online), i decided to post them here, for future reference. I will also give the basic idea of how a python cgi uploading script works. The focus is on security of the code.

So, the following is a very simple html form, which will be used as the user interface for the upload.

We suppose that the cgi script is called upload.py and is placed inside the $Web root$/cgi-bin/ directory.

upload.html

<html>

<head> <title>Upload Example</title> </head>

<body> <div align=”center”>

<form action=”/cgi-bin/upload.py” method=”POST” enctype=”multipart/form-data”>

File : <input name=”file” type=”file” size=”35″><BR>
<P><input name=”submit” type=”submit” value=”Upload”>

</div> </body> </html>

(more…)

 

Faust’s Monolog 26 January, 2008

Filed under: Philosophy — Nikolas Karalis @ 4:21 pm

One of the most beautiful examples of German literature, is Goethe’s Faust.
***

Today, when I found a few verses of a Goethe’s poem in an interesting book

that I’m reading these days, the following verses from Faust came to my mind.

***

I used to know them when I was younger and repeat them from time to time, so here they are…

***

A beautiful soundtrack is The Damnation of Faust by Hector Berlioz

in addition to the classic Szenen aus Goethe’s Faust by Robert Schumann

which can be found here.

***

You can find an English translation of the drama here.

*** ***

***

***

***


Faust

Johann Wolfgang von Goethe

Habe nun, ach! Philosophie,
Juristerei und Medizin,
Und leider auch Theologie
Durchaus studiert, mit heißem Bemühn.
Da steh’ ich nun, ich armer Tor,
Und bin so klug als wie zuvor!

***


Heiße Magister, heiße Doktor gar,
Und ziehe schon an die zehen Jahr’
Herauf, herab und quer und krumm
Meine Schüler an der Nase herum -
Und sehe, daß wir nichts wissen können!
Das will mir schier das Herz verbrennen.

***


Zwar bin ich gescheiter als alle die Laffen,
Doktoren, Magister, Schreiber und Pfaffen;
Mich plagen keine Skrupel noch Zweifel,
Fürchte mich weder vor Hölle noch Teufel -

***


Dafür ist mir auch alle Freud’ entrissen,
Bilde mir nicht ein, was Rechts zu wissen,
Bilde mir nicht ein, ich könnte was lehren,
Die Menschen zu bessern und zu bekehren.

***


Auch hab’ ich weder Gut noch Geld,
Noch Ehr’ und Herrlichkeit der Welt;
Es möchte kein Hund so länger leben!
Drum hab’ ich mich der Magie ergeben,
Ob mir durch Geistes Kraft und Mund
Nicht manch Geheimnis würde kund;

***


Daß ich nicht mehr mit sauerm Schweiß
Zu sagen brauche, was ich nicht weiß;
Daß ich erkenne, was die Welt
Im Innersten zusammenhält,
Schau’ alle Wirkenskraft und Samen,
Und tu’ nicht mehr in Worten kramen.







 




























Millenium Problems Bet 26 January, 2008


Filed under: Mathematics, Science — Nikolas Karalis @ 1:46 am 
 





Like the Hawking-Thorne bet, we have been talking with my good friend and fellow mathematician Primelude about the Clay Millennium Problems and if and how they are going to be solved. For a few of them we agree and for others not. So we decided to bet on that. We will post our predictions, and wait if and how some of these are going to be solved. The bet is a one year subscription to a (scientific? :-P  ) magazine of the winners choice.


So here are my predictions…



It will be proved to be True, using tools from the Etale cohomology.



Probably False. Counterexample will be found.



Probably will be proved to be False. But even if it turns out to be True,

computationally (–> practically),  P will still be not equal to NP.



************************








Grigori Perelman




************************







Smooth solutions always exist for both Navier-Stokes Equations and Euler Equations.



True. I can even predict who is going to prove it, if it happens in the next 30 years.


No! I’m not telling you! ;-) 


My guess, it is going to happen by finding attributes of the distribution of the primes.


Com’ on! I almost said who! :-P 


Btw, i think that if one of the 7 problems is unsolvable,then this is the one.









There exists a theory and it can explain the mass gap… True, true true! :-) 




And now we sit and wait! Or try to win the bet (together with the 1.000.000$) :-P 




P.S.

On Goldbach conjecture :


I believe it is true, but it will take us at least 100 more years before it is being solved.




 




























Les chants de Maldoror 23 January, 2008


Filed under: Mathematics, Philosophy — Nikolas Karalis @ 12:26 am 
 





After finding out about some verses from Les Chants de Maldoror, the wonderful work of Comte de Lautréamont (1846 – 1870), I decided to translate this passage (relatively loose translation) into English (from French) so people like me who don’t speak French, can enjoy the beauty of it and the admiration of Lautréamont for the magnificent glory of mathematics.


It took me a decent amount of time, since i have no idea about French and even less about poetry and poetic translations.


So take this as a warning! :-P 


I hope that soon i will be able to present also a Greek translation.


Note : The image a bellow is the engraving Melencolia I, a work of art by the German Renaissance master Albrecht Dürer. Many books and interpretations have been written about this excellent composition, so i will not even try to describe and i will only refer you to Wikipedia or other sources of informations about it.






Le Chants de Maldoror,  Comte de Lautréamont












Arithmetic! Algebra! Geometry! Grandiose trinity! Luminous triangle!






Whoever has not known you is without sense!






He would deserve to suffer the greatest tortures;






since there is blind contempt for his ignorant indifference.






but the one who has met you, never again desires the goods of the earth






and he only seeks your magic pleasure.






And concentrating on your recondite wings, only wants to elevate over a spiral staircase,






and towards the sphere ædicule (gates) of heaven.






Earth only provides moral phantasmagoria and  illusions,






but you, o mathematics concise, through the rigorous and unswerving propositions and the iron consistency of your rules,






you shine in his dazzled eyes, reflecting the power of the Supreme Truth,  embossed in the order of the universe.






But this surrounding order, which is revealed in the regularity of Pythagoras’s friend, the  perfect square, is even greater,






since Deity (Almighty – God) has presented his existence and his attributes ultimately in this notorious work,






bringing from the bowels of chaos the treasure of your theorems and the magnificent splendors.






From ancients times to now, many people of great imagination have been  enchanted by the thought of your symbols,






presented on paper, as all mysterious signs which are not understood by the profane hordes.






These symbols were only the shining revelations of eternal axioms and hieroglyphs,






which have existed before the existence of Universe and  will remain true after the end of it…








Melencolia I


 (more…)




 




























Synæsthesia & Algebra 18 January, 2008


Filed under: Mathematics, Science — Nikolas Karalis @ 5:53 pm 
 





Synæsthesia is the neurological condition where the stimulation of a cognitive pathway leads to the involuntary stimulation of another cognitive pathway. In simple English, it mean that when for example you see a number, your brain reacts as if you have seen a color. This also happens for shapes, letters, sounds etc.


People under the influence of psychedelic drugs can sometimes feel it (the popular “hear the colors and see the sounds” effect) or even people after a stroke.


The most common explanations are two.


1) The cross-activation of adjacent regions of the brain which are involved in the color and numbers/letters recognition.


2)  The reduction in the amount of inhibition along feedback pathways (can explain the LSD/mescaline effects).


But what do all of these have to do with Algebra?


Well, last night while studying Algebra (from the wonderful textbook  A First Course in Abstract Algebra – J.Fraleigh, which i highly recommend) i stopped on a phrase saying that the Dihedral D4 symmetry group is simple and beautiful.


And this is true. D4 is beautiful. But how can you see that in this Cayley table?





o
I
T
R
R2
R3
RT
R2T
R3T




I
I
T
R
R2
R3
RT
R2T
R3T




T
T
I
R3T
R2T
RT
R3
R2
R




R
R
RT
R2
R3
I
R2T
R3T
T




R2
R2
R2T
R3
I
R
R3T
T
RT




R3
R3
R3T
I
R
R2
T
RT
R2T




RT
RT
R
T
R3T
R2T
I
R3
R2




R2T
R2T
R2
RT
T
R3T
R
I
R3




R3T
R3T
R3
R2T
RT
T
R2
R
I





I believe that the following representation is much better for seeing the underlying beauty and symmetry.




So, i decided to create a web application for doing exactly this. You provide the Cayley table of the group, and it returns you the color representation of it.


You can find it here : http://papaya.hep.ntua.gr/projects/algebra/


For any suggestions/problems, fell free to contact me.




 




























Unlocking Knowledge, Empowering Minds. 14 January, 2008


Filed under: Science — Nikolas Karalis @ 9:47 pm 
 





The last few months, I am viewing the Physics III (Vibrations and Waves) video lectures from MIT.


So, I am writing this post, in order to express my appreciation and my support to MIT’s effort with OpenCourseWare to provide free and quality knowledge for everyone.  I always believed that this effort is important and original, but know that I’m using it in a more systematic way i see that it is a really useful tool (especially for people who don’t have access to academic education).




The second reason I’m writing this, is to inform you about one of the best professors I’ve ever  had the pleasure to attend their lecture.


I’m speaking of Walter Lewin, the physics professor at MIT who teaches the Physics I, II and III there.


The things he is doing are not even close to anything else I’ve ever seen in a classroom.


He jumped on a huge pendulum to present the idea that period doesn’t change with mass.


He inhaled Helium to prove that the velocity of sound in Helium is 3 times more than in air.


He broke a glass with a special device which produces high frequency sound, to display the ω–> ω0 effects.


He brought a whole orchestra of students to play in front of a microphone connected to an oscilloscope to explain the different sound quality of each instrument.


and many many more…


You can find many of his videos online, and you can also download his lectures from OCW.




 




























Introduction to Algorithms (Greek Translation) 13 January, 2008


Filed under: Computers — Nikolas Karalis @ 7:09 pm 
 





The following post is written in Greek. It is my complains about the Greek translation of the classic book : “Introduction to Algorithms“, T. Cormen et al.


Αυτές τις μέρες και με αφορμή κάποιες ασκήσεις Αλγορίθμων και γραφημάτων, σκέφτηκα να εκμεταλευτώ την ελληνική μετάφραση του κλασικού βιβλίου Αλγορίθμων των Cormen, Leiserson, Rivest, Stein απο MIT Press, που εκδόθηκε πέρυσι στην Ελλάδα απο τις Πανεπιστημιακές Εκδόσεις Κρήτης (ΠΕΚ).




Οι ΠΕΚ είναι κατα τη γνώμη μου απο τις καλύτερες εκδόσεις στην Ελλάδα, με πλήθος αξιόλογων βιβλίων. Και είχα χαρεί πολύ για την μετάφραση αυτού του πολύ καλού βιβλίου. Αλλά πραγματικά, είναι μια απο τις χειρότερες μεταφράσεις βιβλίων που έχω διαβάσει ποτέ.


Όπως αναφέρεται στον πρόλογο του επιμελήτη :


“Μία απο τις κύριες μέριμνες των ΠΕΚ είναι η προσεκτική χρήση της ελληνικής γλώσσας… Ένα απο τα σημαντικά προβλήματα που έπρεπε να επιλυθούν στη συγκεκριμένη έκδοση ήταν η εύστοχη απόδοση στα ελληνικά της σχετικής επιστημονικής ορολογίας, και η συνεπής τήρηση των όποιων ορολογικών επιλογών καθ’ όλη την υπο έκδοση σειρά.”


Και τα κατάφεραν. Μετέφρασαν κάθε αγγλική λέξη στα ελληνικά, και μάλιστα σε λέξεις που προσωπικά δεν έχω ξανακούσει να χρησιμοποιούνται. Και γίνεται σε τέτοια έκταση που μοιάζει με αυτόματη μετάφραση του Google. Φυσικά δεν κρίνω την ορθή χρήση


των ελληνικών απο τον μεταφραστή αλλά την υπερβολική και (κατά τη γνώμη μου) ενοχλητική και λανθασμένη μετάφραση των επιστημονικών όρων. Πραγματικά λυπάμαι τον άνθρωπο που θα δοκιμάσει να χρησιμοποιήσει αυτό το βιβλίο για να μάθει αλγόριθμους. Προσωπική μου εκτίμηση είναι οτι καλύτερα να αγοράσει κάποιος την αγγλική έκδοση (η οποία κοστιζει 55 ευρώ) παρά την ελληνική (της οποίας ο πρώτος τόμος μόνο κοστίζει 40).


Δεν θα έμπαινα στον κόπο να γράψω για αυτό το θέμα, αλλά κάθε φορά που ανοίγω αυτό το βιβλίο, με πιάνει πονοκέφαλος απο την ακατανόητη μετάφραση.




 




























Caffeine 8 January, 2008


Filed under: Science — Nikolas Karalis @ 2:20 am 
 





          A mathematician is a machine for turning coffee into theorems. – Alfréd Rényi


After pulling an allnighter last night, in order to stay awake during the day i needed huge amounts of coffee.


So i decided to write a post (the first of a series of posts on this subject) about the neurological effects of this miraculous drug called caffeine.


 <WARNING – Organic Chemistry>


Caffeine is trimethylxanthine and is found in plants to protect them from various insects.


It is metabolized in the liver, to 3 dimethylxanthines (replacing CH3 with H) which have their own distinct but physiological effects :


Paraxanthine, Theobromine and Theophylline


So, how does caffeine works?


Caffeine has a similar structure to adenosine, which is used in ATP and ADP (the “energy credits” of the cells) and is also an inhibitory neurotransmitter. As neurotransmitter, the main action of adenosine is probably to promote sleep.


(HINT: A receptor is a protein in the cell. where molecules can bind and promote a cellular response)


Due to the similar structure, after crossing the blood brain barrier (or : when it is in the brain) caffeine acts as an antagonist of the A1 and A2A adenosine receptors (and Theophylline acts as an antagonist for the other two). This means, that it binds on the receptors, and prohibits the adenosine  binding. This fact stimulates the release of dopamine.


Furthermore, caffeine increases the production of serotonin, epinephrine and gastric acid.


The main effects of the 3 metabolites of caffeine are :


Paraxantine : Increases lipolysis (“more  energy for the muscles”)


Theobromine :  Dilates the vessels, resulting in increased supplies of oxygen and nutrients to the brain and the muscles.


Theophylline : Increases heart rate and efficiency.


Dopamine is a neurotransmitter, which bind on the Dopamine receptors, who control motivation, pleasure and learning.


Dopamine in the mesolimbic pathway (a neural pathway of the brain) decreases latent inhibition and promotes arousal.


This facts, induce the creativity and idea generation. However, very high levels of dopamine in the mesolimbic pathway are connected with psychosis and schizophrenia.


 </WARNING – Organic Chemistry>


The subject of Creativity, Caffeine, and Latent Inhibition which was the main reason i was prompted to write about caffeine, will be addressed in a later post.


P.S. Biochemistry is a topic where my knowledge is really limited. So most of my information for writing this post came from books and Internet. I found writing this post a good exercise  of writing for something you don’t know much, while avoiding plagiarism.




 




























Python Hacking 7 January, 2008


Filed under: Programming — Nikolas Karalis @ 5:43 am 
 









Efficiency Tips 




In this post, i will try to collect tips and tricks for efficient Python programming. Feel free to contribute.


I will update every once in a while, so check back…


    

  • Fastest string conversion :
    • 



>>> a=123


>>> `a` 


'123'


    

  •  Fastest string concatenation :
    • 



>>> ''.join['a','b','c'] 


Efficiency comparison


Optimization Anecdote (Guido van Rossum)


    

  • Generator Functions
    • 



>>> a=[1,2,3]


>>> b=[x**2 for x in a] 


b=[1,4,9]


    

  •  Timing a process :
    • 



from time import clock


t=clock()


... 


t=clock()-t


 (more…)




 




























Deleting duplicate lines from file 5 January, 2008


Filed under: Programming — Nikolas Karalis @ 10:27 pm 
 





I’ve been fighting with a computational problem for many days, but i haven’t even come close to an acceptable solution.


The problem statement :


Given a file of n lines, return the index number of the duplicate lines (where index line is 0 for the first line, 1 for the 2nd etc.)


It may sound trivial, even silly, but i can assure you it is not. It can be relatively simple for small number of lines.


But as n raises, the problem becomes exponentially harder.


When i first faced the problem, i had to deal with a few hundred thousands of lines.  So, i came up with a simple  python code to do it.


When the first difficulties appeared, i came up with a faster solution.


  def duplicates(sequence):
	visited={}
	dupl=[]
	for x in sequence:
		if x in visited: dupl.append(x)
		visited[x]=1
	return dupl


However, now that i have to find the duplicate lines in files with 15 million. 26 million and more, it is impossible to use this code, since it returns memory errors.


So i found another idea, which is REALLY slow for now.


    

  1. Sort the file with the windows or unix command : sort
    2. 

  2. Use unix command uniq -d, to get a list of the duplicated lines.
    3. 

  3. Use unix command grep -n, on the unsorted file for every line in the previous list, to get which lines are duplicated.
    4. 

  4. Use a simple python script to parse the result and get only the the integers we are interested in.
    5. 



However, the grep part is REALLY slow for huge files. So, my problem remains. However, i reduced the problem from removing duplicated from a file, to simply getting fast the index of a line in a file or equivalently, fast iteration and comparison of the file lines.


After extended digging in the Internet, i was not able to find any efficient algorithm or implementation.