Search

Cohen and Lenstra have given a heuristic which, for a fixed odd prime p, leads to many interesting predictions about the distribution of p-class groups of imaginary quadratic fields. We extend the Cohen-Lenstra heuristic to a non-abelian setting by considering, for each imaginary quadratic field K, the Galois group of the p-class tower of K, i.e. $${G}_K:=\mathrm {Gal}(K_\infty /K)$$ where $$K_\infty $$ is the maximal unramified p-extension of K. By class field theory, the maximal abelian quotient of $${G}_K$$ is isomorphic to the p-class group of K. For integers $$c\ge 1$$ , we give a heuristic of Cohen-Lenstra type for the maximal p-class c quotient of $${G}_K$$ and thereby give a conjectural formula for how frequently a given p-group of p-class c occurs in this manner. In particular, we predict that every finite Schur $$\sigma $$ -group occurs as $$G_K$$ for infinitely many fields K. We present numerical data in support of these conjectures.

Jones and Boston conjectured that the factorization process for iterates of irreducible quadratic polynomials over finite fields is approximated by a one-step Markov model. In this paper, we find unexpected and intricate behavior for some quadratic polynomials, in particular for those whose critical orbits have large cycle and small tail. We also propose a multistep Markov model that explains these new observations better than the model of Jones and Boston.

Tail-biting trellises are important graphical representations of codes, which can be simpler to decode than conventional trellises. While conventional trellises are well understood, the general theory of (tail-biting) trellises is still under development. In this paper we first develop a new algebraic framework for a systematic analysis of linear trellises which enables us to address open foundational questions. In particular, we present a useful and powerful characterization of linear trellis isomorphy. We also obtain a new proof of the linear factorization theorem of Koetter/Vardy, and point out unnoticed problems for the group case. Next, we apply our framework to: 1) describe all the factorizations of linear trellises; 2) determine and classify all the minimal linear trellises for a given linear code; and 3) prove that nonmergeable, one-to-one, linear trellises are determined by the edge-label sequences of certain closed paths. We also provide new insight into mergeability and state how results on reduced linear trellises can be extended to nonreduced ones. Our classification results are relevant to iterative/linear programming decoding, as we show that minimal linear trellises can yield different pseudocodewords even if they have the same graph structure.

The Belgian chocolate problem involves maximizing a parameter {\delta} over a non-convex region of polynomials. In this paper we detail a global optimization method for this problem that outperforms previous such methods by exploiting underlying algebraic structure. Previous work has focused on iterative methods that, due to the complicated non-convex feasible region, may require many iterations or result in non-optimal {\delta}. By contrast, our method locates the largest known value of {\delta} in a non-iterative manner. We do this by using the algebraic structure to go directly to large limiting values, reducing the problem to a simpler combinatorial optimization problem. While these limiting values are not necessarily feasible, we give an explicit algorithm for arbitrarily approximating them by feasible {\delta}. Using this approach, we find the largest known value of {\delta} to date, {\delta} = 0.9808348. We also demonstrate that in low degree settings, our method recovers previously known upper bounds on {\delta} and that prior methods converge towards the {\delta} we find., Comment: 15 pages

Quasi-Quadratic Residue Codes (QQR Codes) are a family of double circulant codes. They are important in at least two respects: Firstly, they have very good minimum distances when p ≡ 3 (mod 8), providing a critical test case for Goppa's Conjecture. Secondly, they serve as a powerful tool for studying point distributions on hyperelliptic curves. We will use the result of their weight distributions to prove a variant on a result of Larsen [1] on asymptotic normal distribution of numbers of points on hyperelliptic curves.

We consider the weight distribution of the binary cyclic code of length 2^n-1 with two zeros @a^a,@a^b. Our proof gives information in terms of the zeta function of an associated variety. We carry out an explicit determination of the weight distribution in two cases, for the cyclic codes with zeros @a^3,@a^5 and @a,@a^1^1. These are the smallest cases of two infinite families where finding the weight distribution is an open problem. Finally, an interesting application of our methods is that we can prove that these two codes have the same weight distribution for all odd n.

We propose a space-time block coding framework based on linear precoding. The codes for P transmit antennas are formed by transmitting the information vector (with P independent information symbols) L times where each time it is rotated by a distinct precoding matrix. The framework generalizes conventional spatial multiplexing techniques and facilitates tradeoff between rate and diversity. We propose a simple construction for precoding matrices whose parameters are chosen to guarantee maximal diversity using algebraic number theory. Our codes exhibit circular structure, which greatly simplifies the performance analysis and facilitates linear decoding. Theoretical analysis and numerical simulations demonstrated excellent performance of the proposed algebraic precoding framework.

Let \(G_{\mathbb{Q}}\) be the absolute Galois group of \(\mathbb{Q}\), and let T be the complete rooted d-ary tree, where d ≥ 2. In this article, we study “arboreal” representations of \(G_{\mathbb{Q}}\) into the automorphism group of T, particularly in the case d = 2. In doing so, we propose a parallel to the well-developed and powerful theory of linear p-adic representations of \(G_\mathbb{Q}\). We first give some methods of constructing arboreal representations and discuss a few results of other authors concerning their size in certain special cases. We then discuss the analogy between arboreal and linear representations of \(G_{\mathbb{Q}}\). Finally, we present some new examples and conjectures, particularly relating to the question of which subgroups of Aut(T) can occur as the image of an arboreal representation of \(G_{\mathbb{Q}}\).

Very little is known regarding the Galois group of the maximal p-extension unramified outside a finite set of primes S of a number field in the case that the primes above p are not in S. We describe methods to compute this group when it is finite and conjectural properties of it when it is infinite.

Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete $d \times N$ matrix is finitely rank-$r$ completable if there are at most finitely many rank-$r$ matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its unique completability. The main contribution of this paper is a deterministic sampling condition for finite completability. We use this to also derive deterministic sampling conditions for unique completability that can be efficiently verified. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if $O(\max\{r,\log d\})$ entries per column are observed. These findings have several implications on LRMC regarding lower bounds, sample and computational complexity, the role of coherence, adaptive settings and the validation of any completion algorithm. We complement our theoretical results with experiments that support our findings and motivate future analysis of uncharted sampling regimes., This update corrects an error in version 2 of this paper, where we erroneously assumed that columns with more than r+1 observed entries would yield multiple independent constraints

Tail-biting-trellis representations of codes allow for iterative decoding algorithms, which are limited in effectiveness by the presence of pseudocodewords. We introduce a multivariate weight enumerator that keeps track of these pseudocodewords. This enumerator is invariant under many linear transformations, often enabling us to compute it exactly. The extended binary Golay code has a particularly nice tail-biting-trellis and a famous unsolved question is to determine its minimal AWGN pseudodistance. The new enumerator provides an inroad to this problem.

An extension of a polynomial consists of the polynomial plus higher power terms. Given a polynomial with real coefficients and an integer larger than its degree, a method is given that produces a finite list of extensions of degree this larger integer such that this list necessarily contains the extension whose largest root is as small as possible. This extension is called the pole radius minimizer. The pole radius minimizer is then found by the finite check of comparing the polynomials in the list. The method is applied to obtain filter transformations that are optimal as regards throughput, but also have considerable savings in hardware overhead compared with standard methods such as Scattered Lookahead and Minimum Order Augmentation. The table in Section 5 gives an explicit comparison for various kinds of filters.

In this paper we introduce a new method for finding Galois groups by computer. This is particularly effective in the case of Galois groups of p-extensions ramified at finitely many primes but unramified at the primes above p. Such Galois groups have been regarded as amongst the most mysterious objects in number theory. Very little has hitherto been discovered regarding them despite their importance in studying p-adic Galois representations unramified at p. The conjectures of Fontaine-Mazur say that they should have no p-adic analytic quotients (equivalently, the images of the Galois representations should always be finite), and there are generalizations due to the first author, suggesting that they should instead have `large' actions on certain trees. The idea is to modify the p-group generation algorithm so that as it goes along, it uses number-theoretical information to eliminate groups that cannot arise as suitable quotients of the Galois group under investigation. In the best cases we obtain a short list of candidates for the Galois group. This leads to various conjectures.

There are many results on the minimum distance of a cyclic code of the form that if a certain set T is a subset of the defining set of the code, then the minimum distance of the code is greater than some integer t. This includes the BCH, Hartmann-Tzeng, Roos, and shift bounds and generalizations of these. In this paper we define certain projective varieties V(T,t) whose properties determine whether, if T is in the defining set, the code has minimum distance exceeding t. Thus our attention shifts to the study of these varieties. By investigating them using class field theory and arithmetical geometry, we will prove various new bounds. It is interesting, however, to note that there are cases that existing methods handle, that our methods do not, and vice versa. We end with a number of conjectures.

In network information theory, Shannon-type inequalities are not enough to describe the entropy regions if there are more than three random variables. The Ingleton inequality is one of the most interesting and useful non-Shannon-type inequalities in four random variables. It is satisfied by linear network codes, but not by all network codes. A measure of how much it fails by is given by the Ingleton score. The Four-Atom Conjecture of R. Dougherty, C Freiling, and K. Zeger states that the Ingleton score cannot exceed 0.089373. Using groups to characterize the entropy region, we propose a two-dimensional extension of the Ingleton score, which yields finer information. In particular, we conjecture constraints on this two-dimensional Ingleton score, i.e. a refinement of the Four-Atom Conjecture. Also, we present two families of examples that between them produce all permissible two-dimensional Ingleton scores.

(1995). The World's Most Famous Math Problem (The Proof of Fermat's Last Theorem and Other Mathematical Mysteries). By Marilyn vos Savant. The American Mathematical Monthly: Vol. 102, No. 5, pp. 470-473.

In network information theory, non-Shannon-type inequalities arise in determining capacity/entropy regions where there are more than three random variables. The most famous such inequality is the Ingleton inequality, which is satisfied by linear network codes. To produce better network codes raises the question of finding points in the region that violate the Ingleton inequality and this problem can be translated into group theory. Abelian and small groups do not produce violations, and Mao, Thill, and Hassibi computed that the smallest Ingleton-violating group is the symmetric group on five letters, of order 120. They then generalized this example to other matrix groups. In each of their cases, the Ingleton ratio (which is less than or equal to 1 if and only if the inequality holds) is smaller than 4/3. We go beyond their work to show that examples of Ingleton-violating groups abound, construct explicit examples with arbitrarily large Ingleton ratio, give a systematic approach to finding good examples and a much simplified formula for the Ingleton ratio, and give supporting evidence for the Four-Atom Conjecture of Dougherty, Freiling, and Zeger, which would bound the ratio in terms of the group order.

We present a new algebraic framework for linear trellises which yields a new and simpler proof of the fundamental Factorization Theorem by Koetter and Vardy [4], and which sheds light on several other foundational questions that were not considered before. The techniques used within this framework are new, and comprise algebraic tools that can be used to analyze systematically the structure of linear trellises. In fact our methods and tools produce several subsequent results, the most important of which are: characterization of linear trellises isomorphy, uniqueness of linear structure of linearizable trellises, methods for determining all possible factorizations of trellises. These same algebraic methods have a potential for extending the Factorization Theorem to the case of group trellises. In fact this is very important, since the Factorization Theorem for group trellises as formulated by Koetter and Vardy is false.

Tail-biting trellises and their pseudocodewords are very important for modern decoding techniques like iterative decoding. We introduce a useful matrix representation of trellises, give its fundamental properties, and use it to enumerate and describe the distribution of trellis pseudocodewords. We give several examples, a couple of which lead to important open problems. Next, we prove that the pseudocodeword weight enumerator introduced in [2] always satisfies a recurrence equation, and, for certain trellises including the Golay trellis given in [3], that it is invariant under generalized MacWilliams transformations, allowing invariant theory to be used for computing it. Computation for the Golay trellis shows then that pseudocodewords of period at most 4 must have AWGN pseudoweight at least 8.

In 1990 Hendrik W. Lenstra, Jr. asked the following question: if G is a transitive permutation group of degree n and A is the set of elements of G that move every letter, then can one find a lower bound (in terms of n) for f(G) = |A|/|G|? Shortly thereafter, Arjeh Cohen showed that 1 n is such a bound. Lenstra’s problem arose from his work on the number field sieve [2]. A simple example of how f(G) arises in number theory is the following: if h is an irreducible polynomial over the integers, consider the proportion

For each n, we consider whether there exists an (n + 1)-dimensional space of n by n matrices over GF(2) in which each nonzero matrix has rank n−1. Examples are given for n =3 ,4, and 5, together with evidence for the conjecture that none exist for n>8.

We produce infinitely many finite 2-groups that do not embed with index 2 in any group generated by involutions. This disproves a conjecture of Lemmermeyer and restricts the possible Galois groups of unramified 2-extensions, Galois over Q, of quadratic number fields.

We describe methods for explicit computation of Galois groups of certain tamely ramified p-extensions. In the finite case this yields a short list of candidates for the Galois group. In the infinite case it produces a family or few families of likely candidates.

Hyperelliptic curve cryptography with genus larger than one has not been seriously considered for cryptographic purposes because many existing implementations are significantly slower than elliptic curve versions with the same level of security. In this paper, the first ever complete hardware implementation of a hyperelliptic curve coprocessor is described. This coprocessor is designed for genus two curves over F2113. Additionally, a modification to the Extended Euclidean Algorithm is presented for the GCD calculation required by Cantor's algorithm. On average, this new method computes the GCD in one-fourth the time required by the Extended Euclidean Algorithm.

The IEEE Signal Processing Society (2000) offered a prize of $1000 for proving or disproving Makhoul's conjecture, which says that, given a causal all-pass digital signal x/sub n/ of order p, with nonzero x/sub 0/, the location of the peak of x/sub n/ always lies between n = 0 and n = 2p-1. The case of p = 1 is trivial, and no further progress had been made in 25 years until Lertniphonphun, Rajagopal, and Wenzel gave counter examples for large p. In this paper, Makhoul's conjecture is proven for p = 2. It is also shown that the conjecture fails dramatically in the case of complex coefficients.

There is an old problem that asks for the probability that two integers chosen at random are relatively prime. The informal solution goes as follows.