A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Codes from lattice and related graphs, and permutation decoding

Codes of length n² and dimension 2n−1 or 2n−2 over the field F_p, for any prime p, that can be obtained from designs associated with the complete bipartite graph K_n,n and its line graph, the lattice graph, are examined. The parameters of the codes for all primes are obtained and PD-sets are found for full permutation decoding for all integers n≥3.     

On the Littlewood cyclotomic polynomials

In this article, we study the cyclotomic polynomials of degree N−1 with coefficients restricted to the set {+1,−1}. By a cyclotomic polynomial we mean any monic polynomial with integer coefficients and all roots of modulus 1. By a careful analysis of the effect of Graeffe's root squaring algorithm on cyclotomic polynomials, P. Borwein and K.K. Choi gave a complete characterization of all cyclotomic polynomials with odd coefficients. They also proved that a polynomial p(x) with coefficients ±1 of even degree N−1 is cyclotomic if and only if p(x)=±Φp₁(±x)Φp₂(±xp₁)?Φpr(±xp₁p₂?pr−1), where N=p₁p₂?pr and the pi are primes, not necessarily distinct. Here is the pth cyclotomic polynomial. Based on substantial computation, they also conjectured that this characterization also holds for polynomials of odd degree with ±1 coefficients. We consider the conjecture for odd degree here. Using Ramanujan's sums, we solve the problem for some special cases. We prove that the conjecture is true for polynomials of degree α²pβ−1 with odd prime p or separable polynomials of any odd degree.     

On squares in Lucas sequences

Let P and Q be non-zero integers. The Lucas sequence {Un(P,Q)} is defined by U₀=0, U₁=1, Un=PUn−1−QUn−2 (n?2). The question of when Un(P,Q) can be a perfect square has generated interest in the literature. We show that for n=2,…,7, Un is a square for infinitely many pairs (P,Q) with gcd(P,Q)=1; further, for n=8,…,12, the only non-degenerate sequences where gcd(P,Q)=1 and Un(P,Q)=□, are given by U₈(1,−4)=²¹², U₈(4,−17)=⁶²⁰², and U₁₂(1,−1)=¹²².     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

On the coefficients of ternary cyclotomic polynomials

We study coefficients of ternary cyclotomic polynomials Φ_pqr(z)=∏_ρ(z−ρ), where p, q, and r are distinct odd primes and the product is taken over all primitive pqrth roots of unity ρ.     

Boundedness in Nonlinear Asymmetric Oscillations

In this paper, the boundedness of all solutions of the nonlinear equation (?_p(x′))′+(p-1)[α?_p(x⁺)−β?_p(x⁻)]+f(x)+g(x)=e(t) is discussed, where e(t)∈C⁷ is 2π_p-periodic, f,g are bounded C⁶ functions, ?_p(u)=∣u∣^p−2u, p?2,α,β are positive constants, x⁺=max{x,0},x⁻=max{−x,0}.     

On binary equations

Letb ₁,b ₂ be any positive integers such that (b ₁,b ₂)=1 andm either 1 or 2 satisfyingb ₁+b ₂≡m (mod 2). Letp denote a prime andP ₃ >0 be a product of at most three primes. By sieve methods the author proves that for any δ>0 there exists a positive constantC depending only on δ such thatb ₁ p?b ₂ P ₃=m has a solution inp,P ₃ each less thanC ^(maxb) _j ^δ.     

An extremal problem for algebraic polynomials with zero mean value on an interval

LetP _n ^O(h) be the set of algebraic polynomials of degreen with real coefficients and with zero mean value (with weighth) on the interval [?1, 1]: $$\smallint _{ - 1}^1 h(x)p_n (x) dx = 0;$$ hereh is a function which is summable, nonnegative, and nonzero on a set of positive measure on [?1, 1]. We study the problem of the least possible value $$i_n (h) = \inf \{ \mu (p_n ):p_n \in \mathcal{P}_n^0 \} $$ of the measure μ(P _n)=mes{x∈[?1,1]:P _n(x)≥0} of the set of points of the interval at which the polynomialp _n∈P _n ^O is nonnegative. We find the exact value ofi _n(h) under certain restrictions on the weighth. In particular, the Jacobi weight $$h^{(\alpha ,\beta )} (x) = (1 - x)^\alpha (1 + x)^\beta $$ satisfies these restrictions provided that ?1<α, β≤0.     

Existence and asymptotic behavior for elliptic equations with singular anisotropic potentials

We study the equation Δu+u|u|^p−1+V(x)u+f(x)=0 in Rn, where n?3 and p>n/(n−2). The forcing term f and the potential V can be singular at zero, change sign and decay polynomially at infinity. We can consider anisotropic potentials of form h(x)|x|⁻² where h is not purely angular. We obtain solutions u which blow up at the origin and do not belong to any Lebesgue space Lr. Also, u is positive and radial, in case f and V are. Asymptotic stability properties of solutions, their behavior near the singularity, and decay are addressed.     

A Leibniz differentiation formula for positive operators

Is is shown that for n→+∞ the Leibnizian combination L′_n(fg)−fL′_n(g)−gL′_n(f) converges uniformly to zero on a compact interval W if the positive operators L_n belong to a certain class (including Bernstein, Gauss-Weierstrass and many others), and if the moduli of continuity of f,g satisfy ω_W(f;h)ω_W(g;h)=o(h) as h→0+. A counterexample shows that Lipschitz conditions are not appropriate to bring about a second-order version of this formula.     

Random and Deterministic Triangle Generation of Three-Dimensional Classical Groups III

Let p₁, p₂, p₃ be primes. This is the final paper in a series of three on the (p₁, p₂, p₃)-generation of the finite projective special unitary and linear groups PSU ₃(pⁿ), PSL ₃(pⁿ), where we say a noncyclic group is (p₁, p₂, p₃)-generated if it is a homomorphic image of the triangle group T_{p1, p2, p3} . This article is concerned with the case where p₁ = 2 and p₂ ≠ p₃. We determine for any primes p₂ ≠ p₃ the prime powers pⁿ such that PSU ₃(pⁿ) (respectively, PSL ₃(pⁿ)) is a quotient of T = T_{2, p2, p3} . We also derive the limit of the probability that a randomly chosen homomorphism in Hom(T, PSU ₃(pⁿ)) (respectively, Hom(T, PSL ₃(pⁿ))) is surjective as pⁿ tends to infinity.     

Uniqueness implies existence and uniqueness conditions for nonlocal boundary value problems for nth order differential equations

For the nth order differential equation, y(n)=f(x,y,y^′,…,y(n−1)), we consider uniqueness implies existence results for solutions satisfying certain nonlocal (k+2)-point boundary conditions, 1?k?n−1. Uniqueness of solutions when k=n−1 is intimately related to uniqueness of solutions when 1?k?n−2. These relationships are investigated as well.     

Odd prime values of the Ramanujan tau function

We study the odd prime values of the Ramanujan tau function, which form a thin set of large primes. To this end, we define LR(p,n):=τ(p ^n?1) and we show that the odd prime values are of the form LR(p,q) where p,q are odd primes. Then we exhibit arithmetical properties and congruences of the LR numbers using more general results on Lucas sequences. Finally, we propose estimations and discuss numerical results on pairs (p,q) for which LR(p,q) is prime.     

Note on a Fermat-type diophantine equation

Let p>5 be a prime number and ζ a pth root of unity. Let c be an integer divisible only by primes of the form kp−1,(k,p)=1.Let C_p⁽ⁱ⁾ be the eigenspace of the p-Sylow subgroup of ideal class group C of corresponding to ωi,ω being the Teichmuller character.In this article we extend the main theorem in Sitaraman (J. Number Theory 80 (2000) 174) and get the following: For any fixed odd positive integer n<p−4, assume:

(a)

At least one of C_p⁽³⁾,C_p⁽⁵⁾,…,C_p⁽ⁿ⁾ is non-trivial.

(b)

C_p⁽ⁱ⁾=0 for p−n−1?i?p−2.

(c)

for 1?i?n+1.

Let q be an odd prime such that , and such that there is a prime ideal Q over q in whose ideal class is of the form I^pJ where J is non-trivial, not a pth power and J∈C_p⁽³⁾⊕C_p⁽⁵⁾⊕?⊕C_p⁽ⁿ⁾.For such p and q, if x^p+y^p=pcz^p has a non-trivial solution , with (x,y,z)=1, then .Let t(n)=n²²⁴ⁿ⁴. If , then applying a result of Soulé (J. Reine Angew. Math. 517 (1999) 209), we show that the above result holds with only condition (a) because the others are automatically satisfied.We also make a remark about the effect of Soulé's result on the p-divisibility of h_p⁺ (the class number of the maximal real subgroup of ) which is relevant to the existence of integral solutions to x^p+y^p=pcz^p.     

Hermite pseudospectral approximations. An error estimate

We find an error bound for the pseudospectral approximation of a function in terms of Hermite functions, hn(x)=e−x²Hn(x), in certain weighted Sobolev spaces. We use properties of Hermite polynomials, as well as an asymptotic expression for their largest zeroes to achieve the mentioned estimate.     

Uniform and mean approximation by certain weighted polynomials,with applications

LetW(x):= exp(-{tiQ(x})), where, for example, Q(x) is even and convex onR, and Q(x)/logx → ∞ asx → ∞. A result of Mhaskar and Saff asserts that ifa _n =a _n (W) is the positive root of the equation $$n = ({2 \mathord{\left/ {\vphantom {2 \pi }} \right. \kern-\nulldelimiterspace} \pi })\int_0^1 {{{a_n xQ'(a_n x)} \mathord{\left/ {\vphantom {{a_n xQ'(a_n x)} {\sqrt {1 - x^2 } }}} \right. \kern-\nulldelimiterspace} {\sqrt {1 - x^2 } }}dx,}$$ then, given any polynomialP _n(x) of degree at mostn, the sup norm ofP _n(x)W(a _n x) overR is attained on [-1, 1]. In addition, any sequence of weighted polynomials {p _n (x)W(a _n x)} ₁ ^∞ that is uniformly bounded onR will converge to 0, for ¦x¦>1. In this paper we show that under certain conditions onW, a function g(x) continuous inR can be approximated in the uniform norm by such a sequence {p _n (x)W(a _n x)} ₁ ^∞ if and only if g(x)=0 for ¦x¦? 1. We also prove anL _p analogue for 0W(x)=exp(?|x| ^α ), when α >1. Further applications of our results are upper bounds for Christoffel functions, and asymptotic behavior of the largest zeros of orthogonal polynomials. A final application is an approximation theorem that will be used in a forthcoming proof of Freud's conjecture for |x| ^p exp(?|x| ^α ),α > 0,p > ?1.     

On the density of odd integers of the form (p − 1)2−n and related questions

It is shown that odd integers k such that k · 2ⁿ + 1 is prime for some positive integer n have a positive lower density. More generally, for any primes p₁, …, p_r, the integers k such that k is relatively prime to each of p₁,…, p_r, and such that k · p₁^n₁p₂^n₂ … p_r^n_r + 1 is prime for some n₁,…, n_r, also have a positive lower density.