Commits

Volker Braun  committed 280fbff

preparing for sage-5.6

  • Participants
  • Parent commits 1ab745f

Comments (0)

Files changed (9)

File 13889_disable_osx.patch

+# HG changeset patch
+# Parent c0d18d9bd1bbedbdc925ba5fb8eddd69a8a92945
+
+Disable enhanced backtraces on OSX
+
+diff --git a/c_lib/src/interrupt.c b/c_lib/src/interrupt.c
+--- a/c_lib/src/interrupt.c
++++ b/c_lib/src/interrupt.c
+@@ -350,9 +350,12 @@
+         "------------------------------------------------------------------------\n");
+     print_backtrace();
+ 
++#ifndef __APPLE__
++    /* See http://trac.sagemath.org/13889 for how Apple screwed this up */
+     fprintf(stderr,
+         "------------------------------------------------------------------------\n");
+     print_enhanced_backtrace();
++#endif
+ 
+     fprintf(stderr, 
+         "------------------------------------------------------------------------\n"

File 13889_sagelib_review.patch

+# HG changeset patch
+# User Jeroen Demeyer <jdemeyer@cage.ugent.be>
+# Date 1358026912 -3600
+# Node ID bb5e3005d41f66880d56c3fd2cf39cc27f5ddd75
+# Parent  913c3849ac5f3bb5af57567d9940e8bb30891f29
+Run sage-CSI: reviewer patch
+
+diff --git a/c_lib/src/interrupt.c b/c_lib/src/interrupt.c
+--- a/c_lib/src/interrupt.c
++++ b/c_lib/src/interrupt.c
+@@ -323,46 +323,64 @@
+ }
+ 
+ 
+-void print_enhanced_backtrace()
++static void print_enhanced_backtrace()
+ {
++    /* Flush all buffers before forking */
++    fflush(stdout);
++    fflush(stderr);
++
+     pid_t parent_pid = getpid();
+     pid_t pid = fork();
+-    if (pid == 0) { // child
+-        char pid_str[10];
+-        snprintf(pid_str, 10, "%i", parent_pid);
+-        execlp("sage-CSI", "sage-CSI", 
+-               "--no-color", "--pid", pid_str, NULL);
++
++    if (pid < 0)
++    {
++        /* Failed to fork: no problem, just ignore */
++        perror("fork");
++        return;
++    }
++
++    if (pid == 0) { /* child */
++        /* We deliberately put these variables on the stack to avoid
++         * malloc() calls, the heap might be messed up! */
++        char path[1024];
++        char pid_str[32];
++        char* argv[5];
++
++        snprintf(path, sizeof(path), "%s/bin/sage-CSI", getenv("SAGE_LOCAL"));
++        snprintf(pid_str, sizeof(pid_str), "%i", parent_pid);
++        
++        argv[0] = "sage-CSI";
++        argv[1] = "--no-color";
++        argv[2] = "--pid";
++        argv[3] = pid_str;
++        argv[4] = NULL;
++        execv(path, argv);
+         perror("Failed to execute sage-CSI");
+         exit(2);
+-    } else if (pid < 0) {  // failed to fork
+-        fprintf(stderr, "Failed to fork (out of memory?).\n");
+-        exit(2);
+     }
++    /* Wait for sage-CSI to finish */
+     waitpid(pid, NULL, 0);
+ }
+ 
+ 
+ void sigdie(int sig, const char* s)
+ {
++    fprintf(stderr, 
++        "------------------------------------------------------------------------\n");
+     print_backtrace();
+ 
+-    fprintf(stderr, "\n"
+-        "------------------------------------------------------------------------\n"
+-        "%s\n"
+-        "Sage will now try to attach the debugger to get more information.\n"
+-        "------------------------------------------------------------------------\n",
+-        s);
+-    print_enhanced_backtrace();    
++    fprintf(stderr,
++        "------------------------------------------------------------------------\n");
++    print_enhanced_backtrace();
+ 
+-    fprintf(stderr, "\n"
++    fprintf(stderr, 
+         "------------------------------------------------------------------------\n"
+         "%s\n"
+         "This probably occurred because a *compiled* component of Sage has a bug\n"
+         "in it and is not properly wrapped with sig_on(), sig_off(). You might\n"
+         "want to run Sage under gdb with 'sage -gdb' to debug this.\n"
+         "Sage will now terminate.\n"
+-        "------------------------------------------------------------------------\n"
+-        "\n",
++        "------------------------------------------------------------------------\n",
+         s);
+     fflush(stderr);
+ 
 trac_13861_prime_phi_segfault.patch
 trac11768_source_of_dynamic_class.patch
 trac_13826_star_imports_race.patch
+trac_8327-universal_cyclotomic_field-cs.patch
 messaging.patch
 trac_13865_SAGE_DEBUG_documentation.patch
 trac_6391_libGAP.patch
+trac_13959_PPC_fix.patch
+trac_13880_gap_pool_RLIMIT_AS.patch
 trac_13588_improve_libGAP.patch
 trac_13588_exec_fix.patch
-trac_13880_gap_pool_RLIMIT_AS.patch
+trac_13588_manifest.patch
+trac_13588_docbuild.patch
 trac_13881_cython_debug_symbols.patch
 trac_13889_enhanced_backtrace.patch
+13889_sagelib_review.patch
+13889_disable_osx.patch
 trac_13687_Parent_for_groups.patch
 trac_13687_review.patch
 trac_13687_assertions.patch

File trac_13588_docbuild.patch

+# HG changeset patch
+# User Volker Braun <vbraun.name@gmail.com>
+# Date 1358876003 0
+# Node ID 5697d3efcc9789025787340edcc45a7d40981ffc
+# Parent  c9344d1e1410be1d2e8fb5ea19352e545a58b9c7
+Reduce memory usage when building docs
+
+diff --git a/doc/common/build_options.py b/doc/common/build_options.py
+--- a/doc/common/build_options.py
++++ b/doc/common/build_options.py
+@@ -17,3 +17,8 @@
+ #Note that this needs to have the doctrees dir    
+ ALLSPHINXOPTS   = SPHINXOPTS + " " + PAPEROPTS + " "
+ WEBSITESPHINXOPTS = ""
++
++# Minimize GAP/libGAP RAM usage in the builder, docbuild already uses too much
++from sage.interfaces.gap import set_gap_memory_pool_size
++set_gap_memory_pool_size(0)  # will be rounded up to 1M
++
+diff --git a/doc/common/conf.py b/doc/common/conf.py
+--- a/doc/common/conf.py
++++ b/doc/common/conf.py
+@@ -616,4 +616,7 @@
+         app.connect('builder-inited', set_intersphinx_mappings)
+         app.connect('builder-inited', sphinx.ext.intersphinx.load_mappings)
+         app.connect('builder-inited', nitpick_patch_config)
++        # Minimize GAP/libGAP RAM usage when we build the docs
++        from sage.interfaces.gap import set_gap_memory_pool_size
++        set_gap_memory_pool_size(0)  # will be rounded up to 1M
+ 
+diff --git a/sage/interfaces/gap.py b/sage/interfaces/gap.py
+--- a/sage/interfaces/gap.py
++++ b/sage/interfaces/gap.py
+@@ -1082,6 +1082,7 @@
+         if max_workspace_size == None:
+             max_workspace_size = _get_gap_memory_pool_size_MB()
+         cmd += ' -o ' + str(max_workspace_size)
++        cmd += ' -s ' + str(max_workspace_size)
+         cmd += ' ' + os.path.join(SAGE_EXTCODE,'gap','sage.g')
+         Expect.__init__(self,
+                         name='gap',
+diff --git a/sage/libs/gap/util.pyx b/sage/libs/gap/util.pyx
+--- a/sage/libs/gap/util.pyx
++++ b/sage/libs/gap/util.pyx
+@@ -184,24 +184,26 @@
+     # Define argv and environ variables, which we will pass in to
+     # initialize GAP. Note that we must pass define the memory pool
+     # size!
+-    cdef char* argv[8]
++    cdef char* argv[12]
+     argv[0] = "sage"
+     argv[1] = "-l"
+     s = gap_root()
+     argv[2] = s
+ 
+-    from sage.interfaces.gap import get_gap_memory_pool_size
+-    memory_pool = str(get_gap_memory_pool_size())
++    from sage.interfaces.gap import _get_gap_memory_pool_size_MB
++    memory_pool = _get_gap_memory_pool_size_MB()
+     argv[3] = "-o"
+     argv[4] = memory_pool
++    argv[5] = "-s"
++    argv[6] = memory_pool
+                
+-    argv[5] = "-m"
+-    argv[6] = "64m"
++    argv[7] = "-m"
++    argv[8] = "64m"
+    
+-    argv[7] = "-q"    # no prompt!
+-    argv[8] = "-T"    # no debug loop
+-    argv[9] = NULL
+-    cdef int argc = 9
++    argv[9] = "-q"    # no prompt!
++    argv[10] = "-T"    # no debug loop
++    argv[11] = NULL
++    cdef int argc = 11   # argv[argc] must be NULL
+ 
+     # Initialize GAP and capture any error messages
+     # The initialization just prints error and does not use the error handler

File trac_13588_manifest.patch

+# HG changeset patch
+# Parent 84498b98d051901c60ea1c4be1a30d6307a451ab
+
+Add makefile to manifest
+
+diff --git a/MANIFEST.in b/MANIFEST.in
+--- a/MANIFEST.in
++++ b/MANIFEST.in
+@@ -12,6 +12,7 @@
+ include sage/schemes/hyperelliptic_curves/hypellfrob/README
+ graft   sage/server/notebook/templates
+ include sage/tests/french_book/README
++graft   sage/libs/gap/test
+ 
+ recursive-include doc *.rst *.inc
+ graft   doc/common/static

File trac_13880_gap_pool_RLIMIT_AS.patch

 +        if limit >=0:
 +            return limit
 +        else:
-+            avail = self.available_swap() + self.available_ram()
++            avail = self.total_swap() + self.total_ram()
 +            import platform
 +            if platform.architecture()[0] == '32bit':
 +                # 2GB is likely the single-process address space limit
      """
      Provide information from ``/proc/`` pseudo-filesystem on most UNIXes
  
+@@ -114,9 +172,9 @@
+             sage: info   # random output
+             {'available_ram': 1749782528, 
+              'total_swap': 15728635904, 
+-             'available_swap': 15340572672,
++             'free_swap': 15340572672,
+              'total_ram': 16708194304}
+-            sage: keys = set(['available_ram', 'total_swap', 'available_swap', 'total_ram'])
++            sage: keys = set(['available_ram', 'total_swap', 'free_swap', 'total_ram'])
+             sage: (info is None) or keys.issubset(info.keys())
+             True
+         """
+@@ -132,11 +190,11 @@
+             if line[0].startswith('SwapTotal') and line[2] == 'kB':
+                 result['total_swap'] = int(line[1]) * kb
+             if line[0].startswith('SwapFree') and line[2] == 'kB':
+-                result['available_swap'] = int(line[1]) * kb
++                result['free_swap'] = int(line[1]) * kb
+             if line[0].startswith('Committed_AS') and line[2] == 'kB':
+                 result['Committed_AS'] = int(line[1]) * kb
+         meminfo.close()
+-        required = set(['available_ram', 'total_swap', 'available_swap', 'total_ram'])
++        required = set(['available_ram', 'total_swap', 'free_swap', 'total_ram'])
+         if not required.issubset(result.keys()):
+             raise OSError('failed to parse /proc/meminfo correctly')
+         return result
 @@ -184,7 +242,7 @@
          EXAMPLES::
  
              True
          """
          return self._parse_proc_meminfo()['total_swap']
-@@ -200,7 +258,7 @@
+@@ -195,22 +253,23 @@
+         
+         OUTPUT:
+ 
+-        Integer. The free swap size in bytes.
++        Integer. The free swap size in bytes, excluding reserved swap
++        space. Can be negative if the system is overcommitting memory.
+ 
          EXAMPLES::
  
              sage: from sage.misc.memory_info import MemoryInfo
              True
          """
          info = self._parse_proc_meminfo()
-@@ -210,7 +268,7 @@
-             return info['available_swap']
+         try:
+             return info['total_swap'] - info['Committed_AS']
+         except KeyError:
+-            return info['available_swap']
++            return info['free_swap']
  
  
 -class MemoryInfo_OSX(SageObject):
      """
      Memory info on OSX
  
-@@ -320,7 +378,7 @@
+@@ -320,7 +379,7 @@
          EXAMPLES::
  
              sage: from sage.misc.memory_info import MemoryInfo
              True
          """
          return 2*self.total_ram()
-@@ -339,13 +397,13 @@
+@@ -339,13 +398,13 @@
          EXAMPLES::
  
              sage: from sage.misc.memory_info import MemoryInfo
      """
      Guess memory as a fallback.
  
-@@ -401,7 +459,7 @@
+@@ -401,7 +460,7 @@
          EXAMPLES::
  
              sage: from sage.misc.memory_info import MemoryInfo
              True
          """
          GB = 1024 * 1024 * 1024
-@@ -418,9 +476,7 @@
+@@ -418,9 +477,7 @@
          EXAMPLES::
  
              sage: from sage.misc.memory_info import MemoryInfo

File trac_13889_enhanced_backtrace.patch

 # HG changeset patch
 # User Volker Braun <vbraun.name@gmail.com>
 # Date 1356890443 0
-# Node ID 6316386cd94e047e59159449fefd89f2c8b4284f
-# Parent be2c742303035ab14f805e4182350ce79e6798c1
+# Node ID 8c5adc71c0ee0667f927867b6cab7c45c7adfb9a
+# Parent  bf47f1a2c33fb66b70680d9ca87635cf88d3f9ec
 Make sage print and log extended backtrace before dying
 
 diff --git a/c_lib/src/interrupt.c b/c_lib/src/interrupt.c
 --- a/c_lib/src/interrupt.c
 +++ b/c_lib/src/interrupt.c
-@@ -304,6 +304,26 @@
+@@ -304,9 +304,37 @@
  }
  
  
-+void print_backtrace_and_die()
++void print_enhanced_backtrace()
 +{
 +    pid_t parent_pid = getpid();
 +    pid_t pid = fork();
 +        char pid_str[10];
 +        snprintf(pid_str, 10, "%i", parent_pid);
 +        execlp("sage-CSI", "sage-CSI", 
-+               "--no-color", "--kill", "--pid", pid_str, NULL);
++               "--no-color", "--pid", pid_str, NULL);
 +        perror("Failed to execute sage-CSI");
 +        exit(2);
 +    } else if (pid < 0) {  // failed to fork
 +        fprintf(stderr, "Failed to fork (out of memory?).\n");
 +        exit(2);
 +    }
-+    sleep(10);
-+    fprintf(stderr, "We should have been killed by sage-CSI, but nothing happened.\n");
++    waitpid(pid, NULL, 0);
 +}
 +
 +
  void sigdie(int sig, const char* s)
  {
      print_backtrace();
-@@ -313,11 +333,15 @@
-         "This probably occurred because a *compiled* component of Sage has a bug\n"
++
++    fprintf(stderr, "\n"
++        "------------------------------------------------------------------------\n"
++        "%s\n"
++        "Sage will now try to attach the debugger to get more information.\n"
++        "------------------------------------------------------------------------\n",
++        s);
++    print_enhanced_backtrace();    
++
+     fprintf(stderr, "\n"
+         "------------------------------------------------------------------------\n"
+         "%s\n"
+@@ -314,7 +342,8 @@
          "in it and is not properly wrapped with sig_on(), sig_off(). You might\n"
          "want to run Sage under gdb with 'sage -gdb' to debug this.\n"
--        "Sage will now terminate.\n"
+         "Sage will now terminate.\n"
 -        "------------------------------------------------------------------------\n",
-+        "Sage will now try to attach the debugger to get more information and\n"
-+        "and then terminate.\n"
 +        "------------------------------------------------------------------------\n"
 +        "\n",
          s);
      fflush(stderr);
  
-+    print_backtrace_and_die();    
-+
-     /* Suicide with signal ``sig`` */
-     kill(getpid(), sig);
- 
 diff --git a/sage/tests/interrupt.pyx b/sage/tests/interrupt.pyx
 --- a/sage/tests/interrupt.pyx
 +++ b/sage/tests/interrupt.pyx

File trac_13959_PPC_fix.patch

+# HG changeset patch
+# Parent 83b340b2a7ef32b90d2b5acc0211df6e93d32a89
+
+Fix decimal points in "top" output
+
+diff --git a/sage/misc/memory_info.py b/sage/misc/memory_info.py
+--- a/sage/misc/memory_info.py
++++ b/sage/misc/memory_info.py
+@@ -227,6 +227,46 @@
+         except (IOError, ValueError, subprocess.CalledProcessError, KeyError):
+             raise OSError('failed to parse OSX "top" output')
+ 
++    def _parse_top_output(self, meminfo):
++        """
++        Pick total and available memory out of the "top" output
++
++        INPUT:
++
++        - ``meminfo`` -- output of "top"
++
++        OUTPUT:
++
++        See :meth:`_parse_top`.
++
++        TESTS:
++
++            sage: from sage.misc.memory_info import MemoryInfo_OSX
++            sage: m = MemoryInfo_OSX.__new__(MemoryInfo_OSX)
++            sage: osx_ppc = 'PhysMem:  64.7M wired, 87.3M active,  14.1M inactive,  29.3M used,  21.8M free'
++            sage: m._parse_top_output(osx_ppc)
++            {'available_ram': 22858956, 'total_ram': 53582232}
++
++            sage: osx_x86 = 'PhysMem: 8861M wired, 3574M active, 678M inactive, 13G used, 19G free.'
++            sage: m._parse_top_output(osx_x86)
++            {'available_ram': 20401094656L, 'total_ram': 34359738368L}    # 32-bit
++            {'available_ram': 20401094656, 'total_ram': 34359738368}      # 64-bit
++        """
++        units = { 'K': 1024, 'M':1024**2, 'G':1024**3 }
++        for line in meminfo.splitlines():
++            if not line.startswith('PhysMem:'):
++                continue
++            line = line.split()
++            if not line[-1].startswith('free') or not line[-3].startswith('used'):
++                raise OSError('failed to parse PhysMem: line in "top" output')
++            used_ram = line[-4]
++            free_ram = line[-2]
++            used_ram = int( float(used_ram[:-1]) * units[used_ram[-1]])
++            free_ram = int( float(free_ram[:-1]) * units[free_ram[-1]])
++            return { 'total_ram': used_ram + free_ram,
++                     'available_ram': free_ram }
++        raise OSError('failed to parse "top" output, no PhysMem: section')
++
+     def _parse_top(self):
+         """
+         Parse ``top`` output
+@@ -253,26 +293,12 @@
+         import time
+         if (time.time()-self._age) < self._maxage:
+             return self._parse_top_cache
+-        units = { 'K': 1024, 'M':1024**2, 'G':1024**3 }
+-        result = dict()
+         meminfo = subprocess.check_output(['top', '-l', '1'], 
+                                           stderr=subprocess.STDOUT)
+-        for line in meminfo.splitlines():
+-            if not line.startswith('PhysMem:'):
+-                continue
+-            line = line.split()
+-            if not line[-1].startswith('free') or not line[-3].startswith('used'):
+-                raise OSError('failed to parse PhysMem: line in "top" output')
+-            used_ram = line[-4]
+-            free_ram = line[-2]
+-            used_ram = int(used_ram[:-1]) * units[used_ram[-1]]
+-            free_ram = int(free_ram[:-1]) * units[free_ram[-1]]
+-            result = { 'total_ram': used_ram + free_ram,
+-                       'available_ram': free_ram }
+-            self._age = time.time()
+-            self._parse_top_cache = result
+-            return result
+-        raise OSError('failed to parse "top" output, no PhysMem: section')
++        result = self._parse_top_output(meminfo)
++        self._age = time.time()
++        self._parse_top_cache = result
++        return result
+ 
+     def total_ram(self):
+         """

File trac_8327-universal_cyclotomic_field-cs.patch

+# HG changeset patch
+# User Christian Stump <christian.stump at gmail.com>
+# Date 1353496409 -3600
+# Node ID 755050b9a1e7eb8694efb37916e80b398f3f1054
+# Parent  16599825ecde80ff3cf924b3f676c8ac0885974f
+trac 8327: Implementation of the universal cyclotomic field
+
+diff --git a/doc/en/reference/rings_standard.rst b/doc/en/reference/rings_standard.rst
+--- a/doc/en/reference/rings_standard.rst
++++ b/doc/en/reference/rings_standard.rst
+@@ -15,3 +15,5 @@ Standard Commutative Rings
+    
+    sage/rings/finite_rings/constructor
+    sage/rings/finite_rings/element_base
++
++   sage/rings/universal_cyclotomic_field/universal_cyclotomic_field
+diff --git a/module_list.py b/module_list.py
+--- a/module_list.py
++++ b/module_list.py
+@@ -1469,6 +1469,11 @@ ext_modules = [
+     Extension('sage.rings.ring',
+               sources = ['sage/rings/ring.pyx']),
+ 
++    Extension('sage.rings.universal_cyclotomic_field.universal_cyclotomic_field_c',
++              sources = ['sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.pyx'],
++              include_dirs = numpy_include_dirs,
++              depends = numpy_depends),
++
+         ################################
+         ##
+         ## sage.rings.finite_rings
+diff --git a/sage/modules/free_module.py b/sage/modules/free_module.py
+--- a/sage/modules/free_module.py
++++ b/sage/modules/free_module.py
+@@ -181,6 +181,7 @@ import sage.rings.infinity
+ import sage.rings.integer
+ import sage.structure.parent_gens as gens
+ from sage.categories.principal_ideal_domains import PrincipalIdealDomains
++from sage.categories.commutative_rings import CommutativeRings
+ from sage.misc.randstate import current_randstate
+ from sage.structure.sequence import Sequence
+ 
+diff --git a/sage/rings/all.py b/sage/rings/all.py
+--- a/sage/rings/all.py
++++ b/sage/rings/all.py
+@@ -17,6 +17,9 @@ Rings
+ #                  http://www.gnu.org/licenses/
+ #*****************************************************************************
+ 
++# for lazy importing
++from sage.misc.lazy_import import lazy_import
++
+ # Ring base classes
+ from ring import Ring, is_Ring
+ from commutative_ring import CommutativeRing, is_CommutativeRing
+@@ -89,6 +92,7 @@ from real_lazy import RealLazyField, RLF
+ # Polynomial Rings and Polynomial Quotient Rings
+ from polynomial.all import *
+ 
++
+ # Algebraic numbers
+ from qqbar import (AlgebraicRealField, is_AlgebraicRealField, AA,
+                    AlgebraicReal, is_AlgebraicReal,
+@@ -160,3 +164,6 @@ from residue_field import ResidueField
+ from misc import composite_field
+ 
+ import tests
++
++# Universal Cyclotomic Field
++lazy_import("sage.rings.universal_cyclotomic_field.all","*")
+diff --git a/sage/rings/number_field/number_field.py b/sage/rings/number_field/number_field.py
+--- a/sage/rings/number_field/number_field.py
++++ b/sage/rings/number_field/number_field.py
+@@ -19,6 +19,8 @@ AUTHORS:
+ - Robert Harron (2012-08): added is_CM(), complex_conjugation(), and
+   maximal_totally_real_subfield()
+ 
++- Christian Stump (2012-11): added conversion to universal cyclotomic field
++
+ .. note::
+ 
+    Unlike in PARI/GP, class group computations *in Sage* do *not* by default
+@@ -781,84 +783,95 @@ def is_QuadraticField(x):
+ 
+     
+ _cyclo_cache = {}
+-def CyclotomicField(n, names=None, embedding=True):
++def CyclotomicField(n=0, names=None, bracket="()", embedding=True):
+     r"""
+-    Return the n-th cyclotomic field, where n is a positive integer.
+-    
++    Return the `n`-th cyclotomic field, where n is a positive integer,
++    or the universal cyclotomic field if ``n==0``.
++
++    For the documentation of the universal cyclotomic field, see :class:`~sage.rings.universal_cyclotomic_field.universal_cyclotomic_field.UniversalCyclotomicField`.
++
+     INPUT:
+-    
+-    -  ``n`` - a positive integer
+-    
+-    -  ``names`` - name of generator (optional - defaults
+-       to zetan).
+-    
++
++    -  ``n`` - a nonnegative integer, default:``0``
++
++    -  ``names`` - name of generator (optional - defaults to zetan)
++
++    - ``bracket`` - Defines the brackets in the case of ``n==0``, and
++      is ignored otherwise. Can be any even length string, with ``"()"`` being the default.
++
+     -  ``embedding`` - bool or n-th root of unity in an
+        ambient field (default True)
+-    
+-    
+-    EXAMPLES: We create the `7`\th cyclotomic field
++
++    EXAMPLES:
++
++    If called without a parameter, we get the :class:`universal cyclotomic field<sage.rings.universal_cyclotomic_field.universal_cyclotomic_field.UniversalCyclotomicField>`::
++
++        sage: CyclotomicField()
++        Universal Cyclotomic Field
++
++    We create the `7`\th cyclotomic field
+     `\QQ(\zeta_7)` with the default generator name.
+-    
++
+     ::
+-    
++
+         sage: k = CyclotomicField(7); k
+         Cyclotomic Field of order 7 and degree 6
+         sage: k.gen()
+         zeta7
+-    
++
+     The default embedding sends the generator to the complex primitive
+     `n^{th}` root of unity of least argument.
+-    
++
+     ::
+-    
++
+         sage: CC(k.gen())
+         0.623489801858734 + 0.781831482468030*I
+-    
++
+     Cyclotomic fields are of a special type.
+-    
++
+     ::
+-    
++
+         sage: type(k)
+         <class 'sage.rings.number_field.number_field.NumberField_cyclotomic_with_category'>
+-    
++
+     We can specify a different generator name as follows.
+-    
++
+     ::
+-    
++
+         sage: k.<z7> = CyclotomicField(7); k
+         Cyclotomic Field of order 7 and degree 6
+         sage: k.gen()
+         z7
+-    
++
+     The `n` must be an integer.
+-    
++
+     ::
+-    
++
+         sage: CyclotomicField(3/2)
+         Traceback (most recent call last):
+         ...
+         TypeError: no conversion of this rational to integer
+-    
+-    The degree must be positive.
+-    
++
++    The degree must be nonnegative.
++
+     ::
+-    
+-        sage: CyclotomicField(0)
++
++        sage: CyclotomicField(-1)
+         Traceback (most recent call last):
+         ...
+-        ValueError: n (=0) must be a positive integer
+-    
++        ValueError: n (=-1) must be a positive integer
++
+     The special case `n=1` does *not* return the rational
+     numbers::
+-    
++
+         sage: CyclotomicField(1)
+         Cyclotomic Field of order 1 and degree 1
+-    
++
+     Due to their default embedding into `\CC`,
+     cyclotomic number fields are all compatible.
+-    
++
+     ::
+-    
++
+         sage: cf30 = CyclotomicField(30)
+         sage: cf5 = CyclotomicField(5)
+         sage: cf3 = CyclotomicField(3)
+@@ -886,9 +899,12 @@ def CyclotomicField(n, names=None, embed
+         zeta9^3
+     """
+     n = ZZ(n)
+-    if n <= 0:
++    if n == 0:
++        from sage.rings.universal_cyclotomic_field.universal_cyclotomic_field import UniversalCyclotomicField
++        return UniversalCyclotomicField(names=names, bracket=bracket, embedding=embedding)
++    if n < 0:
+         raise ValueError, "n (=%s) must be a positive integer"%n
+-    
++
+     if names is None:
+         names = "zeta%s"%n
+     names = sage.structure.parent_gens.normalize_names(1, names)
+@@ -1256,6 +1272,60 @@ class NumberField_generic(number_field_b
+         else:
+             return w
+ 
++    def _coerce_from_universal_cyclotomic_field(self, x):
++        """
++        Coerce an element of the universal cyclotomic field
++        into this cyclotomic field.
++
++        EXAMPLES::
++
++            sage: CF = CyclotomicField(5)
++            sage: UCF.<E> = UniversalCyclotomicField()
++
++            sage: CF(E(5)) # indirect doctest
++            zeta5
++
++            sage: CF = CyclotomicField(7)
++            sage: CF(E(5)) # indirect doctest
++            Traceback (most recent call last):
++            ...
++            TypeError: The element E(5) cannot be converted to Cyclotomic Field of order 7 and degree 6
++
++            sage: CF = CyclotomicField(10)
++            sage: CF(E(5)) # indirect doctest
++            zeta10^2
++
++        Matrices are correctly dealt with::
++
++            sage: M = Matrix(UCF,2,[E(3),E(4),E(5),E(6)]); M
++            [   E(3)    E(4)]
++            [   E(5) -E(3)^2]
++
++            sage: Matrix(CyclotomicField(60),M) # indirect doctest
++            [zeta60^10 - 1     zeta60^15]
++            [    zeta60^12     zeta60^10]
++
++        Using a non-standard embedding::
++
++            sage: CF = CyclotomicField(5,embedding=CC(exp(4*pi*i/5)))
++            sage: x = E(5)
++            sage: CC(x)
++            0.309016994374947 + 0.951056516295154*I
++            sage: CC(CF(x))
++            0.309016994374947 + 0.951056516295154*I
++
++            sage: UCF.<E> = UniversalCyclotomicField(embedding=None)
++            sage: CF(E(5))
++            Traceback (most recent call last):
++            ...
++            TypeError: The element E(5) cannot be converted to Cyclotomic Field of order 5 and degree 4
++        """
++        from sage.rings.universal_cyclotomic_field.universal_cyclotomic_field import UniversalCyclotomicField
++        assert isinstance(x,UniversalCyclotomicField.Element)
++        if not x.parent()._has_standard_embedding or self._n() % x.field_order():
++            raise TypeError("The element %s cannot be converted to %s"%(x,self))
++        return self(x.to_cyclotomic_field())
++
+     def _Hom_(self, codomain, cat=None):
+         """
+         Return homset of homomorphisms from self to the number field
+@@ -7949,8 +8019,19 @@ class NumberField_cyclotomic(NumberField
+             zeta42^7 - 1
+             sage: k6(b^2)
+             zeta6 - 1
+-        
+-        Coercion of GAP cyclotomic elements is also supported::
++
++        Conversion of elements of the :class:`~sage.rings.universal_cyclotomic_field.universal_cyclotomic_field.UniversalCyclotomicField`::
++
++            sage: CF = CyclotomicField(5)
++            sage: UCF.<E> = UniversalCyclotomicField()
++            sage: CF(E(5))
++            zeta5
++
++            sage: CF = CyclotomicField(10)
++            sage: CF(E(5))
++            zeta10^2
++
++       Coercion of GAP cyclotomic elements is also supported::
+ 
+             sage: CyclotomicField(18)(gap('E(3)')) # indirect doctest
+             zeta18^3 - 1
+@@ -7964,6 +8045,8 @@ class NumberField_cyclotomic(NumberField
+             sage: K(O.1^2 + O.1 - 2)
+             z^2 + z - 2
+         """
++        from sage.rings.universal_cyclotomic_field.universal_cyclotomic_field import UniversalCyclotomicField
++
+         if isinstance(x, number_field_element.NumberFieldElement):
+             if isinstance(x.parent(), NumberField_cyclotomic):
+                 return self._coerce_from_other_cyclotomic_field(x)
+@@ -7971,6 +8054,8 @@ class NumberField_cyclotomic(NumberField
+                 return NumberField_absolute._element_constructor_(self, x)
+         elif sage.interfaces.gap.is_GapElement(x):
+             return self._coerce_from_gap(x)
++        elif isinstance(x,UniversalCyclotomicField.Element):
++            return self._coerce_from_universal_cyclotomic_field(x)
+         elif isinstance(x,str):
+             return self._coerce_from_str(x)
+         else:
+diff --git a/sage/rings/universal_cyclotomic_field/__init__.py b/sage/rings/universal_cyclotomic_field/__init__.py
+new file mode 100644
+--- /dev/null
++++ b/sage/rings/universal_cyclotomic_field/__init__.py
+@@ -0,0 +1,1 @@
++# Initialization file for universal_cyclotomic_field
+diff --git a/sage/rings/universal_cyclotomic_field/all.py b/sage/rings/universal_cyclotomic_field/all.py
+new file mode 100644
+--- /dev/null
++++ b/sage/rings/universal_cyclotomic_field/all.py
+@@ -0,0 +1,1 @@
++from universal_cyclotomic_field import UniversalCyclotomicField
+diff --git a/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.py b/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.py
+new file mode 100644
+--- /dev/null
++++ b/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.py
+@@ -0,0 +1,2039 @@
++r"""
++The universal cyclotomic field (UCF)
++
++Implementation of the universal cyclotomic field using the :meth:`Zumbroich basis<UniversalCyclotomicField.zumbroich_basis_indices>`.
++The universal cyclotomic field is the smallest subfield of the complex field
++containing all roots of unity.
++
++REFERENCES:
++
++.. [Bre97] T. Breuer "Integral bases for subfields of cyclotomic fields" AAECC 8, 279--289 (1997).
++
++AUTHORS:
++
++- Christian Stump
++
++.. NOTE::
++
++    - This function behaves exactly like the *Cyclotomics* in *GAP*.
++    - The universal cyclotomic field is used to work with non-crystallographic
++      reflection groups. E.g., to work with elements as matrices, computing
++      *reflecting hyperplanes*, and *characters*.
++    - To multiply matrices over the universal cyclotomic field, it is still
++      *much* faster to coerce it to a cyclotomic field and to the
++      computation there.
++
++.. TODO::
++
++    - implementation of matrices over the universal cyclotomic field.
++    - speed improvements of the cythonized methods.
++    - speed improvements for scalar multiples.
++    - Remove the inheritance from Field and FieldElement as soon as
++      the methods ``is_field(proof=True)`` is implemented in the Fields category.
++
++
++EXAMPLES:
++
++The universal cyclotomic field is constructed using::
++
++    sage: UCF = UniversalCyclotomicField(); UCF
++    Universal Cyclotomic Field
++
++One can as well construct it through :func:`~sage.ring.number_field.number_field.CyclotomicField`::
++
++    sage: UCF = CyclotomicField(); UCF
++    Universal Cyclotomic Field
++
++The cyclotomics themselves are accessable through::
++
++    sage: UCF.gen(5)
++    E(5)
++    sage: UCF.gen(5,2)
++    E(5)^2
++
++or the alias::
++
++    sage: UCF.gen(5)
++    E(5)
++    sage: UCF.gen(5,2)
++    E(5)^2
++
++One can as well access the universal cyclotomic field using::
++
++    sage: UCF.<E> = UniversalCyclotomicField();
++    sage: E(5)
++    E(5)
++
++Other names are supported as well::
++
++    sage: UCF.<zeta> = UniversalCyclotomicField();
++    sage: zeta(5)
++    zeta(5)
++
++As are other bracketings::
++
++    sage: UCF.<E> = UniversalCyclotomicField(bracket='');
++    sage: E(5)
++    E5
++
++    sage: UCF.<E> = UniversalCyclotomicField(bracket="[]");
++    sage: E(5)
++    E[5]
++
++    sage: UCF.<E> = UniversalCyclotomicField(bracket="(ABCXYZ)");
++    sage: E(5)
++    E(ABC5XYZ)
++
++We use the generator "E" and the standard bracketing throughout this file::
++
++    sage: UCF.<E> = UniversalCyclotomicField();
++
++Some very first examples::
++
++    sage: E(2)
++    -1
++    sage: E(3)
++    E(3)
++    sage: E(6)
++    -E(3)^2
++
++Equality and inequality checks::
++
++    sage: E(6,2) == E(6)^2 == E(3)
++    True
++
++    sage: E(6)^2 != E(3)
++    False
++
++Addition and multiplication::
++
++    sage: E(2) * E(3)
++    -E(3)
++    sage: f = E(2) + E(3); f
++    2*E(3) + E(3)^2
++
++Inverses::
++
++    sage: f^-1
++    1/3*E(3) + 2/3*E(3)^2
++    sage: f.inverse()
++    1/3*E(3) + 2/3*E(3)^2
++    sage: f * f.inverse()
++    1
++
++Complex conjugation::
++
++    sage: f.conjugate()
++    E(3) + 2*E(3)^2
++
++Galois conjugation::
++
++    sage: f.galois_conjugates()
++    [2*E(3) + E(3)^2, E(3) + 2*E(3)^2]
++    sage: f.norm_of_galois_extension()
++    3
++
++Coercion to the algebraic field :class:`QQbar<sage.rings.qqbar.AlgebraicField>`::
++
++    sage: QQbar(E(3))
++    -0.500000000000000? + 0.866025403784439?*I
++    sage: QQbar(f)
++    -1.500000000000000? + 0.866025403784439?*I
++
++Partial conversion to the real algebraic field :class:`AA<sage.rings.qqbar.AlgebraicRealField>`::
++
++    sage: AA(E(5)+E(5).conjugate())
++    0.618033988749895?
++
++    sage: AA(E(5))
++    Traceback (most recent call last):
++    ...
++    TypeError: no conversion of E(5) to the real algebraic field AA
++
++One can as well define the universal cyclotomic field without any embedding::
++
++    sage: UCF.<E> = UniversalCyclotomicField(embedding=None); UCF
++    Universal Cyclotomic Field
++
++    sage: UCF.<E> = UniversalCyclotomicField(embedding=False); UCF
++    Universal Cyclotomic Field
++
++    sage: QQbar(E(5))
++    Traceback (most recent call last):
++    ...
++    TypeError: Illegal initializer for algebraic number
++
++Conversion to :class:`CyclotomicField<sage.rings.number_field.number_field.CyclotomicField>`:
++
++.. WARNING::
++
++    This is only possible if ``self`` has the standard embedding
++
++::
++
++    sage: UCF.<E> = UniversalCyclotomicField()
++
++    sage: E(5).to_cyclotomic_field()
++    zeta5
++
++    sage: f = E(2) + E(3)
++    sage: f.to_cyclotomic_field()
++    zeta3 - 1
++
++    sage: CF = CyclotomicField(5)
++    sage: CF(E(5))
++    zeta5
++
++    sage: CF = CyclotomicField(7)
++    sage: CF(E(5))
++    Traceback (most recent call last):
++    ...
++    TypeError: The element E(5) cannot be converted to Cyclotomic Field of order 7 and degree 6
++
++    sage: CF = CyclotomicField(10)
++    sage: CF(E(5))
++    zeta10^2
++
++Conversions to and from GAP::
++
++    sage: a = gap('E(6)'); a
++    -E(3)^2
++    sage: a.parent()
++    Gap
++
++    sage: b = UCF.from_gap(a); b
++    -E(3)^2
++    sage: b.parent()
++    Universal Cyclotomic Field
++
++    sage: gap(b)
++    -E(3)^2
++
++Conversions to and from the *cyclotomic field*::
++
++    sage: a = E(6).to_cyclotomic_field(); a
++    zeta3 + 1
++
++    sage: UCF.from_cyclotomic_field(a)
++    -E(3)^2
++
++One can also do basic arithmetics with matrices over the universal cyclotomic field::
++
++    sage: m = matrix(2,[E(3),1,1,E(4)]); m
++    [E(3)    1]
++    [   1 E(4)]
++    sage: m.parent()
++    Full MatrixSpace of 2 by 2 dense matrices over Universal Cyclotomic Field
++
++    sage: m^2
++    [                       -E(3) E(12)^4 - E(12)^7 - E(12)^11]
++    [E(12)^4 - E(12)^7 - E(12)^11                            0]
++
++    sage: -m
++    [-E(3)    -1]
++    [   -1 -E(4)]
++
++And compute its *characteristic polynomial*, *echelon form*, *pivots*, and thus its *rank*::
++
++    sage: m.charpoly()
++    x^2 + (-E(12)^4 + E(12)^7 + E(12)^11)*x + E(12)^4 + E(12)^7 + E(12)^8
++
++    sage: m.echelon_form()
++    [1 0]
++    [0 1]
++
++    sage: m.pivots()
++    (0, 1)
++
++    sage: m.rank()
++    2
++
++The eigenvalues do not (yet) work::
++
++    sage: m.eigenvalues() # not implemented
++    ...
++    NotImplementedError:
++
++A long real life test. Computing ``N3`` is much faster than computing
++``N2`` which is again 3 times faster than computing ``N1``::
++
++    sage: W = gap3.ComplexReflectionGroup(14)       #optional - gap3 # long time
++    sage: UC = W.UnipotentCharacters()              #optional - gap3 # long time
++    sage: UCF.<E> = UniversalCyclotomicField();     #optional - gap3 # long time
++    sage: M = matrix(UCF,UC.families[2].fourierMat) #optional - gap3 # long time
++    sage: N1 = M*M                                  #optional - gap3 # long time
++
++    sage: N2 = UCF._matrix_mult(M,M)                #optional - gap3 # long time
++    sage: CF = CyclotomicField(24)                  #optional - gap3 # long time
++    sage: M = matrix(CF,M)                          #optional - gap3 # long time
++    sage: N3 = matrix(UCF,M*M)                      #optional - gap3 # long time
++    sage: N1 == N2 == N3                            #optional - gap3 # long time
++    True
++
++TESTS:
++
++As an indication that everything works, we start with a test that we
++obtain the same answers as in GAP::
++
++    sage: all(str(E(n,k)).translate(None,' ') == gap.execute('E('+str(n)+')^'+str(k)).translate(None,'\n ') for n in range(1,15) for k in range(n))
++    True
++
++The following didn't work first::
++
++    sage: str(-E(9)^4-E(9)^7).translate(None,' ') == gap.execute('-E(9)^4-E(9)^7').translate(None,'\n ')
++    True
++    sage: str(-E(9)^5-E(9)^8).translate(None,' ') == gap.execute('-E(9)^5-E(9)^8').translate(None,'\n ')
++    True
++"""
++#*****************************************************************************
++#       Copyright (C) 2012 Christian Stump <christian.stump@univie.ac.at>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#                  http://www.gnu.org/licenses/
++#*****************************************************************************
++from sage.misc.cachefunc import cached_method
++from sage.misc.lazy_import import lazy_import
++
++from random import randint, randrange, sample, choice
++
++import sage.structure.parent_base
++from sage.structure.unique_representation import UniqueRepresentation
++from sage.structure.element import parent, FieldElement, Element
++from sage.structure.parent import Parent
++
++from sage.structure.element_wrapper import ElementWrapper
++from sage.structure.sage_object import have_same_parent
++
++from sage.categories.morphism import SetMorphism
++from sage.categories.sets_with_partial_maps import SetsWithPartialMaps
++from sage.categories.sets_cat import Sets
++from sage.categories.homset import Hom
++
++from sage.rings.all import ZZ, QQ, CC
++from sage.rings.ring import Field
++from sage.rings.qqbar import QQbar, AA
++from sage.rings.number_field.number_field import CyclotomicField
++from sage.rings.integer import GCD_list, LCM_list
++
++from sage.rings.real_mpfr import RealField, mpfr_prec_min
++from sage.rings.complex_field import ComplexField
++from sage.rings.real_lazy import RLF, CLF
++
++from sage.combinat.dict_addition import dict_linear_combination, dict_addition
++
++from sage.rings.universal_cyclotomic_field.universal_cyclotomic_field_c import ZumbroichBasisCython,push_down_cython,ZumbroichDecomposition,galois_conjugates_cython,push_to_higher_field,dict_multiplication,dict_vector_multiplication
++
++class UniversalCyclotomicField(UniqueRepresentation, Field):
++    r"""
++    The *universal cyclotomic field*, which is the smallest field containing
++    the rational numbers together with all roots of unity.
++
++    Its elements are represented as linear combinations of the so-called
++    *Zumbroich basis*.
++
++    EXAMPLES::
++
++        sage: UCF.<E> = UniversalCyclotomicField(); UCF
++        Universal Cyclotomic Field
++        sage: E(12)
++        -E(12)^7
++        sage: E(12) in UCF
++        True
++
++    One also has access to the universal cyclotomic field using the function :func:`CyclotomicField`::
++
++        sage: UCF = CyclotomicField(); UCF
++        Universal Cyclotomic Field
++
++    One can also construct a vector space over the universal cyclotomic field::
++
++        sage: UCF^3
++        Vector space of dimension 3 over Universal Cyclotomic Field
++    """
++    def __init__(self,names="E",bracket="()",embedding=True):
++        r"""
++
++        :param names: The string name for the root of unity
++        :type names: optional, default:"E"
++        :param bracket: The bracket used in string representations. Can be any even length string
++        :type bracket: optional, default:"()"
++        :param embedding: The given embedding of ``self`` into the complex numbers. Can be
++            - ``True``: The standard embedding
++            - ``None`` or ``False``: No embedding
++            - An indexable `f(n) \in \mathbb{N}` such that `0 \leq f(n) < n` sending the generator ``E(n)`` to `e^{ 2 \pi i k / n }`.
++        :param embedding: optional, default:``True``
++
++        .. WARNING::
++
++            The optional argument ``embedding`` is not checked for consistency.
++
++        TESTS::
++
++            sage: F = UniversalCyclotomicField()
++            sage: TestSuite(F).run()
++        """
++        # the data is stored as linear combinations of elements in the Zumbroich Basis
++        from sage.combinat.free_module import CombinatorialFreeModule
++        from sage.categories.fields import Fields
++        from sage.categories.algebras import Algebras
++
++        # getting the optional argument "names" right
++        if names is None:
++            names = "E"
++        if not isinstance(names,str):
++            if not isinstance(names,(list,tuple)):
++                raise ValueError("The given name %s is not valid"%names)
++            if len(names) != 1:
++                raise ValueError("The given name %s is not valid"%names)
++            names = names[0]
++        if not isinstance(names,str):
++            raise ValueError("The given name %s is not valid"%names)
++
++        # getting the optional argument "bracket" right
++        if isinstance(bracket,str) and len(bracket) % 2 == 0:
++            bracket_len = len(bracket)
++            bracket = (bracket[:bracket_len/2],bracket[bracket_len/2:])
++        else:
++            raise ValueError("The given bracket %s is not a string of even length."%bracket)
++
++        self._data = CombinatorialFreeModule(QQ, ZumbroichBasisIndices(),prefix=names,bracket=bracket)
++        Parent.__init__(self, base = QQ, category = (Fields(), Algebras(QQ)))
++
++        self._has_standard_embedding = False
++        if embedding not in [False,None]:
++            if embedding is True:
++                embedding = lambda n: QQbar.zeta(n)
++                self._has_standard_embedding = True
++
++            P = get_parent_of_embedding(embedding)
++
++           # embedding from self into P
++            def on_basis(x):
++                return embedding(x[0])**(int(x[1]))
++
++            mor = self._data.module_morphism(on_basis, codomain=P)
++            H = SetMorphism(Hom(self, QQbar), lambda z: mor(z.value))
++            self.register_embedding(H)
++
++            # define partial conversions to AA, if possible
++            SetMorphism(
++                    Hom(self, AA, SetsWithPartialMaps()),
++                    lambda elem: elem._real_()
++               ).register_as_conversion()
++
++        # string representations of elements
++        def repr_term(m,type="repr"):
++            if m[1] == 0:
++                return '1'
++            elif 2*m[1] == m[0]:
++                return '-1'
++            elif m[1] == 1:
++                if type == "repr":
++                    return '%s%s%s%s'%(names,bracket[0],m[0],bracket[1])
++                elif type == "latex":
++                    return '\\zeta_{%s}'%m[0]
++            else:
++                if type == "repr":
++                    return '%s%s%s%s^%s'%(names,bracket[0],m[0],bracket[1],m[1])
++                elif type == "latex":
++                    return '\\zeta_{%s}^{%s}'%(m[0],m[1])
++
++        self._data._repr_term = lambda m: repr_term(m,type="repr")
++        self._data._latex_term = lambda m: repr_term(m,type="latex")
++
++        # setting zero and one
++        self._zero = self._from_dict({}, remove_zeros=False)
++        self._one = self._from_dict({(1,0):QQ(1)}, remove_zeros=False)
++
++    @cached_method
++    def gen(self,n, k=1):
++        r"""
++        Returns `\zeta^k` living in :class:`UniversalCyclotomicField`, where `\zeta` denotes the primitive `n`-th root of unity `\zeta = exp(2 \pi i / n)`.
++
++        :param n: positive integer.
++        :param k: positive integer.
++        :type n: integer
++        :type k: integer; optional, default ``1``
++
++        .. NOTE::
++
++            - For the mathematical description of the Zumbroich basis and the
++              algorithmic behind, see [Bre97]_.
++
++            - This function behaves exactly like the *Cyclotomics* in *GAP*.
++
++        EXAMPLES::
++
++            sage: UCF.<E> = UniversalCyclotomicField()
++
++            sage: E(3) # indirect doctest
++            E(3)
++            sage: E(6) # indirect doctest
++            -E(3)^2
++            sage: E(12) # indirect doctest
++            -E(12)^7
++            sage: E(6,2) # indirect doctest
++            E(3)
++            sage: E(6)^2 # indirect doctest
++            E(3)
++        """
++        if n != ZZ(n) or not n > 0 or k != ZZ(k):
++            raise TypeError('The argument for a root of unity is not correct.')
++        else:
++            g = GCD_list([n,k])
++            n = ZZ(n/g)
++            k = ZZ(k/g) % n
++
++        return self._from_dict(push_down_cython(n, ZumbroichDecomposition(n,k)), coerce=True, remove_zeros=False)
++
++    def _first_ngens(self,n):
++        r"""
++        Returns the method :meth:`gen` if ``n=1``, and raises an error otherwise.
++
++        This method is needed to make the following work::
++
++            sage: UCF.<E> = UniversalCyclotomicField() # indirect doctest
++        """
++        if n == 1:
++            return (self.gen,)
++        else:
++            raise ValueError("This ring has only a single generator method.")
++
++    def _element_constructor_(self, arg):
++        r"""
++        The only way to get here is if there was no coercion found.
++
++        In this case, we give other parents the option to define a conversion
++        using the method ``_universal_cyclotomic_field_``, or raise a TypeError otherwise.
++
++        TESTS::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: UCF(CC(5)) # indirect doctest
++            Traceback (most recent call last):
++            ...
++            TypeError: No coercion found for the input 5.00000000000000 with parent Complex Field with 53 bits of precision
++
++            sage: p = Permutation([2,1])
++            sage: UCF(p)
++            Traceback (most recent call last):
++            ...
++            TypeError: No coercion found for the input [2, 1]
++        """
++        if hasattr(arg,"_universal_cyclotomic_field_"):
++            return arg._universal_cyclotomic_field_()
++
++        elif isinstance(arg,(sage.interfaces.gap3.GAP3Element,sage.interfaces.gap.GapElement)):
++            try:
++                return self.from_gap(arg)
++            except:
++                pass
++
++        error_str = "No coercion found for the input %s"%str(arg)
++        if hasattr(arg,"parent"):
++            error_str ="%s with parent %s"%(error_str,str(arg.parent()))
++        raise TypeError(error_str)
++
++    def _coerce_map_from_(self, other):
++        r"""
++        If ``self`` has the standard embedding and
++        - ``other`` is a cyclotomic number field: returns
++          the coercion thereof, taking non-standard embeddings
++          of ``other.parent()`` into account.
++        - ``other`` is also a universal cyclotomic field with the
++          standard embedding: returns the obvious morphism
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: zeta = CyclotomicField(5).gen()
++            sage: UCF(zeta) # indirect doctest
++            E(5)
++
++            sage: zeta = CyclotomicField(5,embedding=CC(exp(2*pi*I/5))).gen()
++            sage: UCF(zeta) # indirect doctest
++            E(5)
++
++            sage: zeta = CyclotomicField(5,embedding=CC(exp(4*pi*I/5))).gen()
++            sage: UCF(zeta) # indirect doctest
++            E(5)^2
++
++            sage: UCF.<E> = UniversalCyclotomicField();
++            sage: UCF2.<E2> = UniversalCyclotomicField();
++            sage: UCF2(E(5))
++            E2(5)
++
++            sage: UCF = UniversalCyclotomicField(embedding=None)
++            sage: UCF(zeta) # indirect doctest
++            Traceback (most recent call last):
++            ...
++            TypeError: No coercion found for the input zeta5 with parent Cyclotomic Field of order 5 and degree 4
++        """
++        from sage.rings.number_field.number_field import NumberField_cyclotomic
++        from sage.rings.number_field.number_field_morphisms import NumberFieldEmbedding
++        if self._has_standard_embedding:
++            if isinstance(other,NumberField_cyclotomic):
++                return  NumberFieldEmbedding(other, self, self.from_cyclotomic_field(other.gen()))
++            elif isinstance(other,UniversalCyclotomicField) and other._has_standard_embedding:
++                return SetMorphism(Hom(other,self), lambda z: self._from_dict(z._dict_()))
++
++    def __pow__(self,n):
++        r"""
++        Returns the ``n``-th power of self as a vector space.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF^3
++            Vector space of dimension 3 over Universal Cyclotomic Field
++        """
++        from sage.modules.free_module import VectorSpace
++        return VectorSpace(self,n)
++
++    def is_finite(self):
++        r"""
++        Returns False as ``self`` is not finite.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.is_finite()
++            False
++        """
++        return False
++
++    def is_subring(self,other):
++        r"""
++        Returns True if ``self`` is a subring of ``other``.
++
++
++        .. WARNING::
++
++            Currently, it is only checked if ``self is other``!
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: UCF.is_subring(UCF)
++            True
++
++            sage: UCF.is_subring(CC)
++            False
++        """
++        return other is self
++
++    def _repr_(self):
++        r"""
++        Returns the string representation of ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF._repr_()
++            'Universal Cyclotomic Field'
++        """
++        return "Universal Cyclotomic Field"
++
++    def _gap_init_(self):
++        r"""
++        Returns gap string representation of ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF._gap_init_()
++            'Cyclotomics'
++        """
++        return 'Cyclotomics'
++
++    def degree(self):
++        r"""
++        Returns the *degree* of ``self`` as a field extension over the Rationals.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.degree()
++            +Infinity
++        """
++        from sage.rings.infinity import infinity
++        return infinity
++
++    def characteristic(self):
++        r"""
++        Returns ``0`` which is the *characteristic* of ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.characteristic()
++            0
++        """
++        return ZZ(0)
++
++    def prime_subfield(self):
++        r"""
++        Returns `\QQ` which is the *prime subfield* of ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.prime_subfield()
++            Rational Field
++        """
++        return QQ
++
++    def is_prime_field(self):
++        r"""
++        Returns False since ``self`` is not a prime field.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.is_prime_field()
++            False
++        """
++        return False
++
++    def an_element(self, order = 3):
++        r"""
++        Returns an element of ``self`` of order ``order``.
++
++        :param order: a positive integer.
++        :type order: integer; optional, default:``3``
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: UniversalCyclotomicField().an_element()
++            E(3)
++
++            sage: UniversalCyclotomicField().an_element(order=6)
++            -E(3)^2
++
++            sage: UniversalCyclotomicField().an_element(order=10)
++            -E(5)^3
++        """
++        return self.gen(order)
++
++    def random_element(self, order=None):
++        r"""
++        Returns a (often non-trivial) pseudo-random element of ``self``.
++
++        :param order:
++        :type order: integer or None; optional, default:``None``
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: UCF.random_element() # random
++            3*E(7)^2 + E(7)^3 + 2*E(7)^4 - 5*E(7)^5
++
++            sage: UCF.random_element(order=4) # random
++            -3*E(4)
++
++            sage: UCF.random_element(order=12) # random
++            E(12)^7 - 4*E(12)^8 + E(12)^11
++        """
++        F = self
++        seq = [-5,-4,-3,-2,-1,1,2,3,4,5]
++        if order is not None:
++            n = order
++        else:
++            n = randint(1, 17)
++        B = ZumbroichBasisIndices().indices(n)
++        # TODO: could this be written in a more conceptual way
++        # by having appropriate constructors?
++        k = randrange(len(B))
++        B = sample(B, k)
++        dict_in_basis = {}
++        for key in B:
++            dict_in_basis[ key.value ] = QQ(choice(seq))
++        return F._from_dict(push_down_cython(n,dict_in_basis), remove_zeros=False)
++
++    def _from_dict(self, D, coerce=True, remove_zeros=True):
++        r"""
++        Returns the element in ``self`` from the given dictionary ``D``.
++
++        :param D: a dictionary with keys being elements in the Zumbroich basis and values being Rationals.
++        :param coerce: if True, the values are coerced to the Rationals.
++        :type coerce: Boolean; optional, default:``False``
++        :param remove_zeros: if True, zeros are removed from the dict first. Should be ``True`` unless it is clear that ``D`` doesn't contain zeros.
++        :type remove_zeros: Boolean; optional, default:``True``
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: D = dict([((1,0),2)])
++            sage: UCF._from_dict(D)
++            2
++
++            sage: D = dict([((1,0),2)],remove_zeros=False)
++            sage: UCF._from_dict(D)
++            2
++
++            sage: D = dict([((1,0),2),((3,1),1),((3,2),0)])
++            sage: UCF._from_dict(D)
++            2 + E(3)
++        """
++        if coerce:
++            for X,a in D.iteritems():
++                D[X] = QQ(a)
++        elem = self.element_class(self._data._from_dict(D, remove_zeros=remove_zeros), parent=self)
++        return elem
++
++    def from_base_ring(self,coeff):
++        r"""
++        Returns the base ring element ``coeff`` as an element in ``self``.
++
++        :param coeff: A rational number.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: x = UCF.from_base_ring(2); x
++            2
++            sage: x.parent()
++            Universal Cyclotomic Field
++        """
++        return self._from_dict({ (1,0):coeff })
++
++    def zero(self):
++        r"""
++        Returns the zero in ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.zero()
++            0
++        """
++        return self._zero
++
++    def one(self):
++        r"""
++        Returns the one in ``self``.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.one()
++            1
++        """
++        return self._one
++
++    def monomial(self, mon, check=True):
++        r"""
++        Returns the monomial in ``self`` associated to ``mon`` in the Zumbroich basis.
++
++        :param mon: an element in the Zumbroich basis
++        :param check: if True, the monomial is checked to be in the Zumbroich basis
++        :type check: Boolean; optional, default:``True``
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: UCF.monomial((1,0))
++            1
++
++            sage: UCF.monomial((4,2))
++            Traceback (most recent call last):
++            ...
++            ValueError: The given data is not a monomial for the UCF.
++        """
++        if check:
++            if not mon in ZumbroichBasisIndices():
++                raise ValueError("The given data is not a monomial for the UCF.")
++        return self._from_dict({ mon : QQ(1) }, remove_zeros=False)
++
++    def sum(self, L):
++        r"""
++        Returns the sum of all elements (which must be coerceable into ``self``) in ``L``.
++
++        :param L: list or tuple of elements in ``self``
++
++        .. NOTE::
++
++            Faster than the usual sum as operated directly on dictionaries, as all steps are done together.
++
++        EXAMPLES::
++
++            sage: UCF.<E> = UniversalCyclotomicField()
++
++            sage: UCF.sum([ E(i) for i in range(1,5) ])
++            E(12)^4 - E(12)^7 - E(12)^11
++        """
++        l = LCM_list([ other.field_order() for other in L ])
++        large_dict_list = [ push_to_higher_field(other.value._monomial_coefficients, other.field_order(), l) for other in L ]
++        return self._from_dict(push_down_cython(l,dict_addition(large_dict_list)), remove_zeros=False)
++
++    def _matrix_mult(self,M1,M2,order=None):
++        r"""
++        Returns the product ``M1`` `\times` ``M2`` of the two matrices ``M1`` and ``M2`` over ``self``.
++
++        .. WARNING::
++
++            This method is not for public use, but only to provide a quick test how fast we can multiply matrices.
++
++        EXAMPLES::
++
++            sage: UCF.<E> = UniversalCyclotomicField()
++
++            sage: M = matrix(UCF,[[E(3),E(4)],[E(5),E(6)]]); M
++            [   E(3)    E(4)]
++            [   E(5) -E(3)^2]
++
++            sage: M2 = UCF._matrix_mult(M,M); M2
++            [-E(60)^4 - E(60)^7 - E(60)^16 - E(60)^28 - E(60)^47 - E(60)^52                                             E(12)^7 - E(12)^11]
++            [                                            E(15)^8 - E(15)^13 -E(60)^7 - E(60)^8 - E(60)^32 - E(60)^44 - E(60)^47 - E(60)^56]
++
++            sage: M2 == M*M
++            True
++        """
++        from sage.matrix.all import zero_matrix
++        if not M1.nrows() == M2.ncols():
++            raise ValueError("The given matrices cannot be multiplied.")
++        dim1, dim, dim2 = M1.ncols(), M1.nrows(), M2.nrows()
++        m_rows = M1.rows()
++        m_cols = M2.columns()
++        rows,cols = [],[]
++        for i in xrange(dim):
++            rows.append(tuple(x.value._monomial_coefficients for x in m_rows[i]))
++            cols.append(tuple(x.value._monomial_coefficients for x in m_cols[i]))
++
++        M_new = zero_matrix(self,dim1,dim2)
++        if order:
++            n = order
++        else:
++            LCM = [ x.field_order() for x in set(M1.list()).union(M2.list()) ]
++            n = LCM_list(LCM)
++        for i in xrange(dim1):
++            for j in xrange(dim2):
++                M_new[i,j] = self._from_dict(push_down_cython(n,dict_vector_multiplication(n,rows[i],cols[j])))
++        return M_new
++
++    def zumbroich_basis_indices(self, n):
++        r"""
++        Returns the indices of the *Zumbroich basis* of order ``n``.
++
++        The Zumbroich basis is a linear basis of the universal cyclotomic field
++        that behaves very well with considering an primitive `d`-th root of unity
++        as a (non primitive) `kd`-th root. See [Bre97]_ for further details.
++
++        :param n: positive integer
++
++        OUTPUT:
++
++        - a set of tuples `(n,k)` of all elements in the Zumbroich basis of order `n`.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.zumbroich_basis_indices(8)
++            set([(8, 1), (8, 3), (8, 0), (8, 2)])
++        """
++        return ZumbroichBasisIndices().indices(n)
++
++    def zumbroich_basis(self,n):
++        r"""
++        Returns the *Zumbroich basis* of order ``n``.
++
++        The Zumbroich basis is a linear basis of the universal cyclotomic field
++        that behaves very well with considering an primitive `d`-th root of unity
++        as a (non primitive) `kd`-th root. See [Bre97]_ for further details.
++
++        :param n: positive integer
++
++        OUTPUT:
++
++        - the set of elements in the universal cyclotomic field forming the Zumbroich basis of order `n`.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.zumbroich_basis(8)
++            set([E(8)^3, 1, E(4), E(8)])
++
++            sage: UCF.zumbroich_basis(9)
++            set([E(9)^2, E(3)^2, E(9)^5, E(9)^4, E(3), E(9)^7])
++        """
++        return set(self.gen(n,k) for n,k in self.zumbroich_basis_indices(n))
++
++    def from_gap(self, elem):
++        r"""
++        Returns the element in ``self`` obtained from the gap by executing ``string``.
++
++        :param string: string representing an element in the universal cyclotomic field
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.from_gap(gap("-E(3)^2"))
++            -E(3)^2
++
++            sage: UCF = UniversalCyclotomicField()
++            sage: UCF.from_gap(gap("E(3)^2"))
++            E(3)^2
++
++            sage: UCF.from_gap(gap("1/6*E(3)")) # testing a former bug
++            1/6*E(3)
++        """
++        if not isinstance(elem,(sage.interfaces.gap3.GAP3Element,sage.interfaces.gap.GapElement)):
++            raise ValueError("the input %s is not a GAP element"%elem)
++        try:
++            return self(elem.sage())
++        except:
++            pass
++        string = str(elem)
++        terms = string.replace('\n','').replace('-','+-').split('+')
++        if terms[0] == '':
++            del terms[0]
++        for i in range(len(terms)):
++            if '^' in terms[i]:
++                terms[i] = terms[i].replace(')^',',') + ')'
++            terms[i] = terms[i].replace("E","self.gen")
++            if '*' in terms[i]:
++                pos = terms[i].index('*')
++                fac = QQ(terms[i][:pos])
++                terms[i] = terms[i][pos+1:]
++            else:
++                fac = None
++            exec('terms[%s]='%i + terms[i])
++            if fac is not None:
++                terms[i] = fac*terms[i]
++        return self.sum(terms)
++
++    def from_cyclotomic_field(self, elem):
++        r"""
++        Returns the element in ``self`` coming from the element in NumberField_cyclotomic.
++
++        :param elem: an element of NumberField_cyclotomic
++
++        .. WARNING::
++
++            This method raises an error if self does not have the standard embedding.
++
++        EXAMPLES::
++
++            sage: UCF = UniversalCyclotomicField()
++
++            sage: a = CyclotomicField(6).gen(); a
++            zeta6
++            sage: UCF.from_cyclotomic_field(a)
++            -E(3)^2
++
++        An example with another embedding::
++
++            sage: a = CyclotomicField(5,embedding=CC(exp(4*pi*I/5))).gen(); a
++            zeta5
++            sage: UCF.from_cyclotomic_field(a)
++            E(5)^2
++
++        TESTS::
++
++            sage: UCF.from_cyclotomic_field(4)
++            Traceback (most recent call last):
++            ...
++            TypeError: the given data (4) is not a cyclotomic field element
++
++            sage: UCF = UniversalCyclotomicField(embedding=None);
++            sage: a = CyclotomicField(5).gen()
++            sage: UCF.from_cyclotomic_field(a)
++            Traceback (most recent call last):
++            ...
++            TypeError: This method can only be used if Universal Cyclotomic Field has the standard embedding
++        """
++        from sage.rings.number_field.number_field import NumberField_cyclotomic
++        if not self._has_standard_embedding:
++            raise TypeError("This method can only be used if %s has the standard embedding"%self)
++        if not hasattr(elem,'parent') or not isinstance(elem.parent(), NumberField_cyclotomic):
++            raise TypeError("the given data (%s) is not a cyclotomic field element"%elem)
++        n = elem.parent()._n()
++        CF = CyclotomicField(n)
++        elem = CF(elem)
++        coeff_list = elem.list()
++        return self._from_dict(push_down_cython(n,dict_linear_combination((ZumbroichDecomposition(n, k), coeff_list[ k ]) for k in range(len(coeff_list)) if coeff_list[k] != 0)), remove_zeros=False)
++
++    class Element(FieldElement, ElementWrapper):
++        r"""
++        An element of the universal cyclotomic field.
++
++        .. SEEALSO::
++
++            - :class:`UniversalCyclotomicField`
++        """
++
++        def __lt__(self,other):
++            r"""
++            Pushes the method forward to ``QQbar``.
++
++            EXAMPLES::
++
++                sage: UCF.<E> = UniversalCyclotomicField()
++                sage: E(3).__lt__(E(4))
++                True
++            """
++            return QQbar(self).__lt__(other)
++
++        def __gt__(self,other):
++            r"""
++            Pushes the method forward to ``QQbar``.