On RSA Moduli with Prescribed Bit Patterns

We give a polynomial time probabilistic algorithm that constructs an RSA modulus M=pl, where p and l are two n-bit primes, which has about n/2 bits, on certain positions, prescribed in advance. Although the number of prescribed bits is less than in other constructions, this algorithm can be rigorously analyzed while the other approaches remain heuristic. The proof is based on bounds of exponential sums. We also show that this algorithm can be used for finding 2n-bit RSA moduli whose binary expansions are of Hamming weight about 3n/4. Finally, similar arguments are also applied to smooth integers.     

Prescribing the binary digits of primes

We present a new result on counting primes p < N = 2 ⁿ for which r (arbitrarily placed) digits in the binary expansion of p are specified. Compared with earlier work of Harman and Katai, the restriction on r is relaxed to r < c(n/log n)^4/7. This condition results from the estimates of Gallagher and Iwaniec on zero-free regions of L-functions with ‘powerful’ conductor.     

On positive entire solutions of indefinite semilinear elliptic equations

We establish that the elliptic equation Δu+K(x)up+μf(x)=0 in Rn has a continuum of positive entire solutions for small μ?0 under suitable conditions on K, p and f. In particular, K behaves like l|x| at ∞ for some l?−2, but may change sign in a compact region. For given l>−2, there is a critical exponent pc=pc(n,l)>1 in the sense that the result holds for p?pc and involves partial separation of entire solutions. The partial separation means that the set of entire solutions possesses a non-trivial subset in which any two solutions do not intersect. The observation is well known when K is non-negative. The point of the paper is to remove the sign condition on compact region. When l=−2, the result holds for any p>1 while pc is decreasing to 1 as l decreases to −2.     

Generalized spherical and simplicial coordinates

Elementary trigonometric quantities are defined in l2,p analogously to that in l2,2, the sine and cosine functions are generalized for each p>0 as functions sinp and cosp such that they satisfy the basic equation p|cosp(φ)|+p|sinp(φ)|=1. The p-generalized radius coordinate of a point ξ∈Rn is defined for each p>0 as . On combining these quantities, ln,p-spherical coordinates are defined. It is shown that these coordinates are nearly related to ln,p-simplicial coordinates. The Jacobians of these generalized coordinate transformations are derived. Applications and interpretations from analysis deal especially with the definition of a generalized surface content on ln,p-spheres which is nearly related to a modified co-area formula and an extension of Cavalieri's and Torricelli's indivisibeln method, and with differential equations. Applications from probability theory deal especially with a geometric interpretation of the uniform probability distribution on the ln,p-sphere and with the derivation of certain generalized statistical distributions.     

Class numbers of cyclotomic fields

In the first part of the paper we show how to construct real cyclotomic fields with large class numbers. If the GRH holds then the class number h_p⁺ of the pth real cyclotomic field satisfies h_p⁺ > p for the prime p = 11290018777. If we allow n to be composite we have, unconditionally, that $\text{h}{}_{\mathrm{n}}{}^{\mathrm{+}}\text{> n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext><mtext>\; ?\; \epsilon </mtext>}}$ for infinitely many n. In the second part of the paper we show that if l ?= 2 mod 4 and n is the product of 4 distinct primes congruent to 1 mod l, then $\text{l}\text{2}$ (l, if l is odd) divides the class number h_n⁺ of the nth cyclotomic field. If the primes are congruent to 1 mod 4l then 2l divides h_n⁺.     

Higher dimensional cable knots and their finite cyclic covering spaces

As an analogue of the classical cable knot, the p-cable n-knot about an n-knot K, where p is an integer and n?2, is defined, and some basic properties of higher dimensional cable knots are described. We show that for p>0 then p-fold branched cyclic covering space of an (n+2)-sphere branched over the p-cable knot about an n-knot K is an (n+2)-sphere or a homotopy (n+2)-sphere which is the result of Gluck-surgery on the composition of p copies of K according as if p is odd or even. At the same time, we prove that for any n?2 and p?2, the composition of p copies of any n-knot K is the fixed point set of a Z_p-action on an (n+2)-sphere. This is another counterexample to the higher dimensional Smith conjecture.     

Short character sums for composite moduli

We establish new estimates on short character sums for arbitrary composite moduli with small prime factors. Our main result improves on the Graham-Ringrose bound for square-free moduli and also on the result due to Gallagher and Iwaniec when the core q′ = Π _p|q p of the modulus q satisfies log q′ ～ log q. Some applications to zero free regions of Dirichlet L-functions and the Pólya and Vinogradov inequalities are indicated.     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Monogamous latin squares

We show for all n∉{1,2,4} that there exists a latin square of order n that contains two entries γ₁ and γ₂ such that there are some transversals through γ₁ but they all include γ₂ as well. We use this result to show that if n>6 and n is not of the form 2p for a prime p?11 then there exists a latin square of order n that possesses an orthogonal mate but is not in any triple of MOLS. Such examples provide pairs of 2-maxMOLS.     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

Pattern Frequency Sequences and Internal Zeros

Let q be a pattern and let S_n, q(c) be the number of n-permutations having exactly c copies of q. We investigate when the sequence (S_n, q(c))_c ≥ 0 has internal zeros. If q is a monotone pattern it turns out that, except for q = 12 or 21, the nontrivial sequences (those where n is at least the length of q) always have internal zeros. For the pattern q = 1(l + 1)l…2 there are infinitely many sequences which contain internal zeros and when l = 2 there are also infinitely many which do not. In the latter case, the only possible places for internal zeros are the next-to-last or the second-to-last positions. Note that by symmetry this completely determines the existence of internal zeros for all patterns of length at most 3.     

Partitions of large multipartites with congruence conditions. II

For 1 ≦ l ≦ j, let $\text{a}$_l = ?_h=1^q(l){a_lh + Mv: v = 0, 1, 2,…}, where j, M, q(l) and the a_lh are positive integers such that j > 1, a_l1 < … < a_lq(2) ≦ M, and let $\text{a}$_l^′ = $\text{a}$_l ∪ {0}. Let p(n : $\text{B}$) be the number of partitions of n = (n₁,…,n_j) where, for 1 ≦ l ≦ j, the lth component of each part belongs to $\text{B}$_l and let p¹(n : $\text{B}$) be the number of partitions of n into different parts where again the lth component of each part belongs to $\text{B}$_l. Asymptotic formulas are obtained for p(n : $\text{a}$), p¹(n : $\text{a}$) where all but one n_l tend to infinity much more rapidly than that n_l, and asymptotic formulas are also obtained for p(n : $\text{a}$′), p¹(n ; $\text{a}$′), where one n_l tends to infinity much more rapidly than every other n_l. These formulas contrast with those of a recent paper (Robertson and Spencer, Trans. Amer. Math. Soc., to appear) in which all the n_l tend to infinity at approximately the same rate.     

The Proof of a Conjecture of Additive Number Theory

The aim of this paper is to show that for any n∈N, n>3, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having the same parity (see the text for the definition of the “length” of a natural number). Also we will show that for any n∈N, n>2, n≠5, 10, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having different parities. We will prove also that for any prime p≡7(mod 8) there exist a, b∈N* such that p=a²+b, the “length” of b being an even number.     

Hecke Eigenfunctions of Quantized Cat Maps Modulo Prime Powers

This paper continues the work done in Olofsson [Commun Math Phys 286(3):1051–1072, 2009] about the supremum norm of eigenfunctions of desymmetrized quantized cat maps. N will denote the inverse of Planck’s constant and we will see that the arithmetic properties of N play an important role. We prove the sharp estimate ||ψ||_∞ = O(N ^1/4) for all normalized eigenfunctions and all N outside of a small exceptional set. We are also able to calculate the value of the supremum norms for most of the so called newforms. For a given N = p ⁿ , with n > 2, the newforms can be divided in two parts (leaving out a small number of them in some cases), the first half all have supremum norm about ${2/\sqrt{1\pm 1/p}}This paper continues the work done in Olofsson [Commun Math Phys 286(3):1051–1072, 2009] about the supremum norm of eigenfunctions of desymmetrized quantized cat maps. N will denote the inverse of Planck’s constant and we will see that the arithmetic properties of N play an important role. We prove the sharp estimate ||ψ||_∞ = O(N ^1/4) for all normalized eigenfunctions and all N outside of a small exceptional set. We are also able to calculate the value of the supremum norms for most of the so called newforms. For a given N = p ⁿ , with n > 2, the newforms can be divided in two parts (leaving out a small number of them in some cases), the first half all have supremum norm about 2/?{1±1/p}{2/\sqrt{1\pm 1/p}} and the supremum norm of the newforms in the second half have at most three different values, all of the order N ^1/6. The only dependence of A is that the normalization factor is different if A has eigenvectors modulo p or not. We also calculate the joint value distribution of the absolute value of n different newforms.     

Equivalent Blocks of Finite General Linear Groups in Non-describing Characteristic

J. Chuang, R. Kessar, and J. Rickard have proved Broué's Abelian defect group conjecture for many symmetric groups. We adapt the ideas of Kessar and Chuang towards finite general linear groups (represented over non-describing characteristic). We then describe Morita equivalences between certain p-blocks of GL_n(q) with defect group C_p^α × C_p^α, as q varies (see Theorem 2). Here p and q are coprime. This generalizes work of S. Koshitani and M. Hyoue, who proved the same result for principal blocks of GL_n(q) when p = 3, α = 1, in a different way.     

Average condition number for solving linear equations

We study an average condition number and an average loss of precision for the solution of linear equations and prove that the average case is strongly related to the worst case. This holds if the perturbations of the matrix are measured in Frobenius or spectral norm or componentwise. In particular, for the Frobenius norm we show that one gains about log₂n+0.9 bits on the average as compared to the worst case, n being the dimension of the system of linear equations.     

Behavior at infinity of solutions of an equation of Osserman-Keller type

We study the behavior at infinity of solutions of equations of the form Δu=u^p, where p>1, in dimensions n?3. In particular we extend results proved by Loewner and Nirenberg in Contribution to Analysis, 1974, pp. 245-272 for the case p=(n+2)/(n−2), n?3, to values of p in the range p>n/(n−2), n?3.     

Geometric Optimization Problems Likely Not Contained in $$\mathbb{A}\mathbb{P}\mathbb{X}$$

   Abstract. Maximizing geometric functionals such as the classical l _p -norms over polytopes plays an important role in many applications, hence it is desirable to know how efficiently the solutions can be computed or at least approximated. While the maximum of the l _∞ -norm over polytopes can be computed in polynomial time, for 2≤ p < ∞ the l _p -norm-maxima cannot be computed in polynomial time within a factor of 1.090 , unless P=NP. This result holds even if the polytopes are centrally symmetric parallelotopes. Quadratic Programming is a problem closely related to norm-maximization, in that in addition to a polytope P ⊂ R ⁿ , numbers c _ij , 1≤ i≤ j≤ n , are given and the goal is to maximize Σ _{1≤ i≤ j≤ n} c _ij x _i x _j over P . It is known that Quadratic Programming does not admit polynomial-time approximation within a constant factor, unless P=NP. Using the observation that the latter result remains true even if the existence of an integral optimal point is guaranteed, in this paper it is proved that analogous inapproximability results hold for computing the l _p -norm-maximum and various l _p -radii of centrally symmetric polytopes for 2≤ p < ∞.