Reverse mathematics of prime factorization of ordinals

One of the earliest applications of Cantor's Normal Form Theorem is Jacobstahl's proof of the existence of prime factorizations of ordinals. Applying the techniques of reverse mathematics, we show that the full strength of the Normal Form Theorem is used in this proof. Received: 13 August 1997 / Revised version: 3 November 1997     

The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}$a\oplus b=\min \{a,b\}$ and a⊗b=a+b$a\otimes b=a+b$. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^m×k$B\in {\mathbf{R}}^{m\times k}$ and C∈R^k×n$C\in {\mathbf{R}}^{k\times n}$ satisfying B⊗C=A$B\otimes C=A$. We show that the TMF problem is NP-hard for every k≥7$k\ge 7$ fixed in advance, thus resolving a problem proposed by Barvinok in 1993.     

Unique prime factorization for infinite tensor product factors

In this article, we investigate a unique prime factorization property for infinite tensor product factors. We provide several examples of type II and III factors which satisfy this property, including all free product factors with diffuse free product components. In the type III setting, this is the first classification result for infinite tensor product non-amenable factors. Our proof is based on Popa's intertwining techniques and a characterization of relative amenability on the continuous cores.     

The conjugacy problem for groups of alternating prime tame links is polynomial-time

An alternating projection of a prime link can to used to produce a group presentation (of the link group under free product with the infinite cyclic group) with some useful peculiarities, including small cancellation conditions. In this presentation, conjugacy diagrams are shown to have the form of a tiling of squares in the Euclidean plane in one of a limited number of shapes. An argument based on the shape of the link projection is used to show that the tiling requires no more square tiles than a linear function of word length (with constant multiple based on the number of link crossings). It follows that the computation time for testing conjugacy of two group elements (previously known to be no worse than exponential) is bounded by a cubic polynomial. This bounds complexity in the original link group.

     

On the parameterized complexity of short computation and factorization

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word can be derived in a grammar in steps, or whether a permutation has a factorization of length over a given set of generators. We show hardness and completeness for these problems for various levels of the hierarchy. In particular, we show that Short TM Computation is complete for . This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. Received August 1, 1994     

On the prime power factorization of n!

In this paper, we prove two results. The first theorem uses a paper of Kim (J. Number Theory 74 (1999) 307) to show that for fixed primes p₁,…,p_k, and for fixed integers m₁,…,m_k, with , the numbers (e_p1(n),…,e_pk(n)) are uniformly distributed modulo (m₁,…,m_k), where e_p(n) is the order of the prime p in the factorization of n!. That implies one of Sander's conjectures from Sander (J. Number Theory 90 (2001) 316) for any set of odd primes. Berend (J. Number Theory 64 (1997) 13) asks to find the fastest growing function f(x) so that for large x and any given finite sequence , there exists n<x such that the congruences hold for all i?f(x). Here, p_i is the ith prime number. In our second result, we are able to show that f(x) can be taken to be at least , with some absolute constant c₁, provided that only the first odd prime numbers are involved.     

On the prime power factorization of n!

For a fixed prime q, let eq(n) denote the order of q in the prime factorization of n!. For two fixed integers m?2 and r with 0?r?m−1, let A(x;m,q,r) denote the numbers of positive integers n?x for which . In this paper we shall prove a sharp asymptotic formula of A(x;m,q,r).     

Lower bounds in communication complexity based on factorization norms

We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives us access to several powerful tools from this area such as normed spaces duality and Grothendiek's inequality. This extends the arsenal of methods for deriving lower bounds in communication complexity. As we show, our method subsumes most of the previously known general approaches to lower bounds on communication complexity. Moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement. Our results also shed some light on the question how much communication can be saved by using entanglement. It is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. It follows from our results that this bound on the saving in communication is tight almost always. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the prime power factorization of n!, II

Let p, q be primes and m be a positive integer. For a positive integer n, let ep(n) be the nonnegative integer with pep(n)|n and pep(n)+1?n. The following results are proved: (1) For any positive integer m, any prime p and any ε∈Zm, there are infinitely many positive integers n such that ; (2) For any positive integer m, there exists a constant D(m) such that if ε,δ∈Zm and p, q are two distinct primes with max{p,q}?D(m), then there exist infinitely many positive integers n such that , . Finally we pose four open problems.     

The factorization of the permanent of a matrix with minimal rank in prime characteristic

It is known that any square matrix A of size n over a field of prime characteristic p that has rank less than n/(p − 1) has a permanent that is zero. We give a new proof involving the invariant X _p . There are always matrices of any larger rank with non-zero permanents. It is shown that when the rank of A is exactly n/(p − 1), its permanent may be factorized into two functions involving X _p .     

On the complexity of the resolvent representation of some prime differential ideals

We prove upper bounds on the order and degree of the polynomials involved in a resolvent representation of the prime differential ideal associated with a polynomial differential system for a particular class of ordinary first order algebraic-differential equations arising in control theory. We also exhibit a probabilistic algorithm which computes this resolvent representation within time polynomial in the natural syntactic parameters and the degree of a certain algebraic variety related to the input system. In addition, we give a probabilistic polynomial-time algorithm for the computation of the differential Hilbert function of the ideal.     

A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function

In this paper we present a refined version of the Newton polygon process to compute the Puiseux expansions of an algebraic function defined over the rational function field. We determine an upper bound for the bit-complexity of computing the singular part of a Puiseux expansion by this algorithm, and use a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions to show that this computational complexity is polynomial in the degrees and the logarithm of the height of the polynomial defining the algebraic function.

     

Some prime factorization results for type II<Subscript>1</Subscript> factors

We prove several unique prime factorization results for tensor products of type II₁ factors coming from groups that can be realized either as subgroups of hyperbolic groups or as discrete subgroups of connected Lie groups of real rank 1. In particular, we show that if is isomorphic to a subfactor in , for some 2r_i,s_j, then mn. Mathematics Subject Classification (2000) Primary 46L10; Secondary 20F67     

A polynomial-time algorithm for near-unanimity graphs

We present a simple polynomial-time algorithm that recognises reflexive, symmetric graphs admitting a near-unanimity operation. Several other characterisations of these graphs are also presented.     

New polynomial-time algorithms for Camion bases

Let M be a finite set of vectors in Rⁿ of cardinality m and H(M)={{x∈Rⁿ:c^Tx=0}:c∈M} the central hyperplane arrangement represented by M. An independent subset of M of cardinality n is called a Camion basis, if it determines a simplex region in the arrangement H(M). In this paper, we first present a new characterization of Camion bases, in the case where M is the column set of the node-edge incidence matrix (without one row) of a given connected digraph. Then, a general characterization of Camion bases as well as a recognition procedure which runs in O(n²m) are given. Finally, an algorithm which finds a Camion basis is presented. For certain classes of matrices, including totally unimodular matrices, it is proven to run in polynomial time and faster than the algorithm due to Fonlupt and Raco.     

A polynomial-time algorithm for finding zero-sums

Erdös, Ginzburg and Ziv proved that any sequence of 2n−1 (not necessary distinct) members of the cyclic group Z_n contains a subsequence of length n the sum of whose elements is congruent to zero modulo n. There are several proofs of this celebrated theorem which combine combinatorial and algebraic ideas. Our main result is an alternative and constructive proof of this result. From this proof, we deduce a polynomial-time algorithm for finding a zero-sum n-sequence of the given (2n−1)-sequence of an abelian group G with n elements (a fortiori for Z_n). To the best of our knowledge, this is the first efficient algorithm for finding zero-sum n-sequences.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

A polynomial-time algorithm for the change-making problem

Optimally making change—representing a given value with the fewest coins from a set of denominations—is in general NP-hard. In most real money systems however, the greedy algorithm is optimal. We give a polynomial-time algorithm to determine, for a given coin system, whether the greedy algorithm is optimal.