On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

On exact coverings of the integers

By an exact covering of modulusm, we mean a finite set of liner congruencesx≡a _i (modm _i ), (i=1,2,...r) with the properties: (I)m _i ∣m, (i=1,2,...,r); (II) Each integer satisfies precisely one of the congruences. Let α≥0, β≥0, be integers and letp andq be primes. Let μ (m) senote the Möbius function. Letm=p ^α q ^β and letT(m) be the number of exact coverings of modulusm. Then,T(m) is given recursively by $$\mathop \Sigma \limits_{d/m} \mu (d)\left( {T\left( {\frac{m}{d}} \right)} \right)^d = 1$$ .     

On the representation of integers by p-adic diagonal forms

Let p be an odd prime, let d be a positive integer such that (d,p?1)=1, let r denote the p-adic valuation of d and let m=1+3+3²+…+3^r. It is shown that for every p-adic integer n the equation Σ_i=1^mX_i^d=n has a nontrivial p-adic solution. It is also shown that for all p-adic units a₁, a₂, a₃, a₄ and all p-adic integers n the equation Σ_i=1⁴a_iX_i^p=n has a nontrivial p-adic solution. A corollary to each of these results is that every p-adic integer is a sum of four pth powers of p-adic integers.     

Universally bad integers and the 2-adics

In his 1964 paper, de Bruijn (Math. Comp. 18 (1964) 537) called a pair (a,b) of positive odd integers good, if , where is the set of nonnegative integers whose 4-adic expansion has only 0's and 1's, otherwise he called the pair (a,b) bad. Using the 2-adic integers we obtain a characterization of all bad pairs. A positive odd integer u is universally bad if (ua,b) is bad for all pairs of positive odd integers a and b. De Bruijn showed that all positive integers of the form u=2^k+1 are universally bad. We apply our characterization of bad pairs to give another proof of this result of de Bruijn, and to show that all integers of the form u=φ_p^k(4) are universally bad, where p is prime and φ_n(x) is the nth cyclotomic polynomial. We consider a new class of integers we call de Bruijn universally bad integers and obtain a characterization of such positive integers. We apply this characterization to show that the universally bad integers u=φ_p^k(4) are in fact de Bruijn universally bad for all primes p>2. Furthermore, we show that the universally bad integers φ_2^k(4), and more generally, those of the form 4^k+1, are not de Bruijn universally bad.     

Powers of cyclotomic integers and difference sets

Let p be an odd prime, $\text{ζ =}\text{rxp}\text{(}\text{2πi}\text{p}\text{)}$, D a difference set mod p having a nontrivial multiplier, and ν = H(ζ), where H(x) is the Hall polynomial of D. For any α = Σ_i=0^p?1a_iζⁱ with rational a_i denote δ(α) = max ∥ a_i ? a_j ∥. Assuming that there are no nontrivial multiplicative dependence relations among the conjugates of ν, we obtain results for

. We then show that for most known families of difference sets mod p the required independence result is valid. A conjecture concerning the exact value of the first number is stated. The conjecture is confirmed in certain particular cases.     

Bases and nonbases of square-free integers

A basis is a set A of nonnegative integers such that every sufficiently large integer n can be represented in the form n = a_i + a_j with a_i, a_i ∈ A. If A is a basis, but no proper subset of A is a basis, then A is a minimal basis. A nonbasis is a set of nonnegative integers that is not a basis, and a nonbasis A is maximal if every proper superset of A is a basis. In this paper, minimal bases consisting of square-free numbers are constructed, and also bases of square-free numbers no subset of which is minimal. Maximal nonbases of square-free numbers do not exist. However, nonbases of square-free numbers that are maximal with respect to the set of square-free numbers are constructed, and also nonbases of square-free numbers that are not contained in any nonbasis of square-free numbers maximal with respect to the square-free numbers.     

The probability that k positive integers are relatively r-prime

If r, k are positive integers, then $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ denotes the number of k-tuples of positive integers (x₁, x₂, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r = 1. An explicit formula for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ is derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}\text{n}{}^{\mathrm{k}}\text{=}\text{1}\text{ζ(rk)}$.If S = {p₁, p₂, …, p_a} is a finite set of primes, then 〈S〉 = {p₁^a₁p₂^a₂…p_s^a_s; p_i ∈ S and a_i ≥ 0 for all i} and $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ denotes the number of k-tuples (x₁, x₃, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r ∈ 〈S〉. Asymptotic formulas for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ are derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}\text{n}{}^{\mathrm{k}}\text{=}\text{(p}{}_1\text{… p}{}_{\mathrm{a}}\text{)}{}^{\mathrm{rk}}\text{ζ(rk)(p}{}_1{}^{\mathrm{rk}}\text{? 1) … (p}{}_{\mathrm{s}}{}^{\mathrm{rk}}\text{? 1)}$.     

Combinational properties of sets of residues modulo a prime and the Erdős—Graham problem

Consider an arbitrary ε > 0 and a sufficiently large prime p > 2. It is proved that, for any integer a, there exist pairwise distinct integers x ₁, x ₂, ..., x _N , where N = 8([1/ε + 1/2] + 1)² such that 1 ≤ x _i ≤ p ^ε, i = 1, ..., N, and $$a \equiv x_1^{ - 1} + \cdots + x_N^{ - 1} (\bmod p)$$ , where x _i ^?1 is the least positive integer satisfying x _i ^?1 x _i ≡ 1 (modp). This improves a result of Sparlinski.     

A better step-off algorithm for the knapsack problem

The knapsack problem, maximize Σ^m_{i = 1}c_ix_i when Σ^m_{i = 1}a_ix_i?b for integers x_i?0, can be solved by the classical step-off algorithm. The algorithm develops a series of feasible solutions with ever-increasing objective values. We make a change in the problem so that the step-off algorithm produces a series of solutions of not necessarily increasing objective values. A point is reached when no better solutions can be found and the calculation is stopped.     

On integers which are the sum of a power of 2 and a polynomial value

Here, we show that if f (x) ∈ ?[x] has degree at least 2 then the set of integers which are of the form 2 ^k + f (m) for some integers k ≥ 0 and m is of asymptotic density 0. We also make some conjectures and prove some results about integers not of the form |2 ^k ± m ^a (m ? 1)|.     

Partitions and sums of integers with repetition

A partition of N is called “admissible” provided some cell has arbitrarily long arithmetic progressions of even integers in a fixed increment. The principal result is that the statement “Whenever {A_i}_{i < r} is an admissible partition of N, there are some i < r and some sequence 〈x_n〉_{n < ω} of distinct members of N such that x_n + x_m?A_i whenever {m, n} ? ω″ is true when r = 2 and false when r ? 3.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) having the ath power (x_i,x_j)^a of the greatest common divisor of x_i and x_j as its i,j-entry divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

On the principles of limiting absorption and limit amplitude for a class of locally perturbed waveguides. Part 1: Time-independent theory

Let Ω be a local perturbation of the n-dimensional domain Ω₀ = Ropf;^{n ? 1} × (0, π). In a previous paper⁸ we have introduced the notion of an admissible standing wave. We shall prove that the principle of limiting absorption holds for the Dirichlet problem of the reduced wave equation in Ω at ω ≥ 0 if Ω does not allow admissible standing waves with frequency ω. From Reference 8, this condition is satisfied for every ω ≥ 0 if Ω ≠ Ω₀, and v · x ′ ≤ 0 on δΩ, where x′ = ( x ₁,…, x_{n ? 1}, 0) and v is the normal unit vector on δΩ pointing into the complement of Ω. In contrast to this, the principle of limiting absorption is violated in the case of the unperturbed domain Ω₀ at the frequencies ω = 1,2,… if n ≤ 3. The second part of our investigation, which will appear in a subsequent paper, is devoted to the principle of limit amplitude.     

Simple continued fractions for the Fredholm numbers

Let {a_i} with a₁ ≥ 2 be an infinite bounded sequence of positive integers, and d₁ = 1, d_i = ±1 for i = 2, 3,…. Let {Q_i} be another sequence defined by the recursion Q₁ = 1, Q_i = a_i?1Q_i?1^k for i = 2, 3,…, where k ≥ 2 an integer. Put C_k(a) = Σ_{i = 1}^∞d_iQ_i^?1. In this paper we shall determine the simple continued fraction expansion for the real numbers C_k(a).     

On the instability of resonances in parallel-plane waveguides

It has been observed¹³ that the propagation of acoustic waves in the region Ω₀= ?² × (0, 1), which are generated by a time-harmonic force density with compact support, leads to logarithmic resonances at the frequencies ω = 1, 2,… As we have shown⁹ in the case of Dirichlet's boundary condition U = 0 on ?Ω, the resonance at the smallest frequency ω = 1 is unstable and can be removed by a suitable small perturbation of the region. This paper contains similar instability results for all resonance frequencies ω = 1, 2,… under more restrictive assumptions on the perturbations Ω of Ω₀. By using integral equation methods, we prove that absence of admissible standing waves in the sense of Reference 7 implies the validity of the principle of limit amplitude for every frequency ω ≥ 0 in the region Ω =Ω₀ ?B, where B is a smooth bounded domain with B??Ω₀. In particular, it follows from Reference 7 in the case of Dirichlet's boundary condition that the principle of limit amplitude holds for every frequency ω ≥ 0 if n · x ′ ? 0 on ? B, where x ′ = (x₁, x₂, 0) and n is the normal unit vector pointing into the interior B of ? B. In the case of Neumann's boundary condition, the logarithmic resonance at ω = 0 is stable under the perturbations considered in this paper. The asymptotic behaviour of the solution for arbitary local perturbations of Ω₀ will be discussed in a subsequent paper.     

The permutation of integers with small least common multiple of two subsequent terms

Erd?s, Freud and Hegyvári [1] constructed a permutation a ₁,a ₂,… of positive integers with \([a_{i}, a_{i+1}]< i\exp \left\{c\sqrt{\log i}\log\log i\,\right\}\) for an absolute constant c>0 and all i≧3. In this note, we construct a permutation of all positive integers such that for any ε>0 there exists an i ₀ with \([a_{i}, a_{i+1}]\allowbreak < i\exp \left\{\left(2\sqrt{2}+\varepsilon\right) \sqrt{\log i\log\log i}\,\right\}\) for all i≧i ₀.     

Good sequences of integers

A sequence (a_j) of integers is α-good (α real) if the sequence (a_jα) of real numbers is uniformly distributed mod 1. For each polynomial P(x) of positive degree with real coefficients, we determine the set of real numbers α for which the sequence of integer parts ([P(j)]) is α-good.     

Indestructibility,HOD, and the Ground Axiom

Let φ₁ stand for the statement V = HOD and φ₂ stand for the Ground Axiom. Suppose T_i for i = 1, …, 4 are the theories “ZFC + φ₁ + φ₂,” “ZFC + ¬φ₁ + φ₂,” “ZFC + φ₁ + ¬φ₂,” and “ZFC + ¬φ₁ + ¬φ₂” respectively. We show that if κ is indestructibly supercompact and λ > κ is inaccessible, then for i = 1, …, 4, A_i = _df{δ < κ∣δ is an inaccessible cardinal which is not a limit of inaccessible cardinals and V_δ?T_i} must be unbounded in κ. The large cardinal hypothesis on λ is necessary, as we further demonstrate by constructing via forcing four models in which A_i = ?? for i = 1, …, 4. In each of these models, there is an indestructibly supercompact cardinal κ, and no cardinal δ > κ is inaccessible. We show it is also the case that if κ is indestructibly supercompact, then V_κ?T₁, so by reflection, B₁ = _df{δ < κ∣δ is an inaccessible limit of inaccessible cardinals and V_δ?T₁} is unbounded in κ. Consequently, it is not possible to construct a model in which κ is indestructibly supercompact and B₁ = ??. On the other hand, assuming κ is supercompact and no cardinal δ > κ is inaccessible, we demonstrate that it is possible to construct a model in which κ is indestructibly supercompact and for every inaccessible cardinal δ < κ, V_δ?T₁. It is thus not possible to prove in ZFC that B_i = _df{δ < κ∣δ is an inaccessible limit of inaccessible cardinals and V_δ?T_i} for i = 2, …, 4 is unbounded in κ if κ is indestructibly supercompact. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On a conjecture of Chowla and Chowla

The equation y² ≡ x(x + a₁)(x + a₂) … (x + a_r) (mod p), where a₁, a₂, …, a_r are integers is shown to have a solution in integers x, y with 1 ≦ x ≦C, where C is a constant depending only on a₁, a₂, …, a_r.