On a kind of generalized Lehmer problem

For 1 ? c ? p ? 1, let E ₁,E ₂, …,E _m be fixed numbers of the set {0, 1}, and let a ₁, a ₂, …, a _m (1 ? a _i ? p, i = 1, 2, …,m) be of opposite parity with E ₁,E ₂, …,E _m respectively such that a ₁ a ₂…a _m ≡ c (mod p). Let $$N(c,m,p) = {1 \over {{2^{m - 1}}}}\mathop {\sum\limits_{{a_1} = 1}^{p - 1} {\sum\limits_{{a_2} = 1}^{p - 1} \ldots } }\limits_{{a_1}{a_2} \ldots \equiv c{\rm{ (}}\bmod {\rm{ }}p)} \sum\limits_{{a_m} = 1}^{p - 1} {(1 - {{( - 1)}^{{a_1} + {E_1}}})(1 - {{( - 1)}^{{a_2} + {E_2}}}) \ldots } (1 - {( - 1)^{{a_m} + {E_m}}}).$$ We are interested in the mean value of the sums $$\sum\limits_{c = 1}^{p - 1} {{E^2}} (c,m,p),$$ where E(c, m, p) = N(c,m, p)?((p ? 1) ^m?1)/(2 ^m?1) for the odd prime p and any integers m ? 2. When m = 2, c = 1, it is the Lehmer problem. In this paper, we generalize the Lehmer problem and use analytic method to give an interesting asymptotic formula of the generalized Lehmer problem.     

Solutions of Semilinear Elliptic Equations in Tubes

Given a smooth compact k-dimensional manifold Λ embedded in ? ^m , with m≥2 and 1≤k≤m?1, and given ?>0, we define B _? (Λ) to be the geodesic tubular neighborhood of radius ? about Λ. In this paper, we construct positive solutions of the semilinear elliptic equation $$\begin{cases} \Delta u + u^p = 0 &\mbox{in } B_{\epsilon}(\varLambda) \\ u = 0 & \mbox{on } \partial B_{\epsilon}(\varLambda) , \end{cases} $$ when the parameter ? is chosen small enough. In this equation, the exponent p satisfies either p>1 when n:=m?k≤2 or $p\in(1, \frac{n+2}{n-2})$ when n>2. In particular, p can be critical or supercritical in dimension m≥3. As ? tends to 0, the solutions we construct have Morse index tending to infinity. Moreover, using a Pohozaev type argument, we prove that our result is sharp in the sense that there are no positive solutions for $p>\frac{n+2}{n-2}$ , n≥3, if ? is sufficiently small.     

A function with prescribed initial derivatives in different Banach spaces

Let X₀ ? X₁ ? ··· ? X_p be Banach spaces with continuous injection of X_k into X_{k + 1} for 0 ? k ? p ? 1, and with X₀ dense in X_p. We seek a function u: [0, 1] → X₀ such that its kth derivative u^(k), k = 0, 1,…, p, is continuous from [0, 1] into x_k, and satisfies the initial condition u^(k)(0) = a_k?X_k. It is shown that such a function exists if and only if the initial values a₀, a₁, …, a_p satisfy a certain condition reminiscent of interpolation theory. This condition always holds when p = 1; when p ? 2, the spaces X_k (k = 0, 1, …, p) may or may not be such that the desired function exists for any given initial values a_k?X_k.     

On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

On a conjecture by B. Grünbaum

Denote by p_k(M) or υ_k(M) the number of k-gonal faces or k-valent of the convex 3-polytope M, respectively. Completely solving a problem by B. Grünbaum, the following theorem is proved: Given sequences of nonnegative integers p = (p₃, p₄,…p_m), υ = (υ₃, υ₄,…,υ_n) satisfying ∑_k?3(6−k)p_k + 2∑_k?3(3−k)υ_k = 12, there exists a convex 3-polytope M with p_k(M) = p_k for all k ≠ 6 and υ_k for all k ≠ 3 if and only if for the sequences p, υ the following does not hold: ∑p_i = 0 for i odd and ∑υ_i = 1 for i ? 0 (mod 3).     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

Hermite series estimates of a probability density and its derivatives

The following estimate of the pth derivative of a probability density function is examined: $\text{Σ}{}_{\mathrm{k\; =\; 0}}{}^{\mathrm{N}}\text{a}\text{?}{}_{\mathrm{k}}\text{h}{}_{\mathrm{k}}\text{(x)}$, where h_k is the kth Hermite function and $\text{a}\text{?}{}_{\mathrm{k}}\text{= (}\text{(?1)}{}^{\mathrm{p}}\text{n}\text{)}$Σ_{i = 1}ⁿh_k^(p)(X_i) is calculated from a sequence X₁,…, X_n of independent random variables having the common unknown density. If the density has r derivatives the integrated square error converges to zero in the mean and almost completely as rapidly as O(n^?α) and O(n^?α log n), respectively, where $\text{α =}\text{2(r ? p)}\text{(2r + 1)}$. Rates for the uniform convergence both in the mean square and almost complete are also given. For any finite interval they are O(n^?β) and $\text{O(n}{}^{\mathrm{<mtext>?\beta </mtext><mtext>2</mtext>}}\text{log}\text{n)}$, respectively, where $\text{β =}\text{(2(r ? p) ? 1)}\text{(2r + 1)}$.     

On the k-polygonal numbers and the mean value of Dedekind sums

For any positive integer k ≥ 3, it is easy to prove that the k-polygonal numbers are a_n(k) = (2n+n(n?1)(k?2))/2. The main purpose of this paper is, using the properties of Gauss sums and Dedekind sums, the mean square value theorem of Dirichlet L-functions and the analytic methods, to study the computational problem of one kind mean value of Dedekind sums S(a_n(k)ā_m(k), p) for k-polygonal numbers with 1 ≤ m, n ≤ p ? 1, and give an interesting computational formula for it.     

The Gelfand–Kirillov dimension of the universal algebras of M a,b (E)⊗E in positive characteristic

In this paper we calculate the Gelfand–Kirillov dimension of the relatively free (also called universal) algebra of rank m, U _m (M _a,b (E)?E), in the variety generated by M _a,b (E)?E, in positive characteristic p>2.     

Completely strong path-connected tournaments

Let T = (V, A) be a tournament with p vertices. T is called completely strong path-connected if for each arc (a, b) ∈ A and k (k = 2, 3,…, p), there is a path from b to a of length k (denoted by P_k(a, b)) and a path from a to b of length k (denoted by P′_k(a, b)). In this paper, we prove that T is completely strong path-connected if and only if for each arc (a, b) ∈ A, there exist P₂(a, b), P′₂(a, b) in T, and T satisfies one of the following conditions: (a) T/T₀-type graph, (b) T is 2-connected, (c) for each arc (a, b) ∈ A, there exists a P′_p?1(a, b) in T.     

Galois stratification over Frobenius fields

New first-order conformally covariant differential operators P_k on spinor-k-forms, i.e., tensor products of contravariant spinors with k-forms, in an arbitrary n-dimensional pseudo-Riemannian spin manifold, are introduced. This provides a series of generalizations of the Dirac operator $\text{?}\text{?}$, in analogy with the series of generalizations (introduced by the author in [1]) of the Maxwell operator and the conformally covariant Laplacian $\text{□}$ on functions. In particular, new intertwining operators for representations of SU(2, 2) and SO(p + 1, q + 1) are found. Related nonlinear covariant operators are also introduced, and mixed nonlinear covariant systems are obtained by coupling to the Yang-Mills-Higgs-Dirac system in dimension 4. The spinor-form bundle is isomorphic with E⁽³⁾ = E ? E ? E, where E is the spin bundle, and the P_k give a covariant operator on sections of E⁽³⁾. This is generalized to a covariant operator on E^{(2l + 1)}. The relation of powers of these operators to higher-order covariant operators on lower spin bundles (analogous to the relation between $\text{?}\text{?}$ and $\text{□}$) is discussed.     

Patterns of power residues

This paper examines the question of whether a given pattern

$\text{x,x+a}{}_1\text{,…,x+a}{}_{\mathrm{m?1}}$

of kth power residues of length m can be postponed indefinitely. This is the case when there exists a prime q, called a delay prime, which does not contain this pattern even if q itself is considered as a kth power residue. It is conjectured that if there exists no delay prime then there exists a finite limit

$\text{Λ=Λ (k,m;a}{}_1\text{,…,a}{}_{\mathrm{m?1}}$

for which the corresponding pattern will occur before Λ in every sufficiently large prime of the form kn + 1.     

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.     

Characterizations of locally testable events

Let Σ be a finite alphabet, Σ^* the free monoid generated by Σ and χ the length of χ ∈ Σ^*. For any integer k0, f_k(χ) (t_k(χ)) is χ if χ < k + 1, and it is the prefix (suffix) of χ of length k, othewise. Also let m_k+1(χ) = {νχ = uνw and ν = k+1}. For χ, y ε Σ^* define χ ～ _k+1y iff f_k(χ) = f_k(y), t_k(χ) = t_k(y) and m_k+1(χ) = m_k+1(y). The relation ～_k+1 is a congruence of finite index over Σ^*. An event E ? Σ^* is (k+1)-testable iff it is a union of congruence classes of ～_k+1. E is locally testable (LT) if it is k+1-testable for some k. (This definition differs from that of [6] but is equivalent.)We show that the family of LT events is a proper sub-family of star-free events of dot-depth 1. LT events and k-testable events are characterized in terms of (a) restricted star-free expressions based on finite and cofinite events; (b) finite automata accepting these events; (c) semigroups; and (d) structural decomposition of such automata. Algorithms are given for deciding whether a regular event is (a) LT and (b) k+1-testable. Generalized definite events are also characterized.     

Blocker sets, orthogonal arrays and their application to combination locks

Let A denote a set of order m and let X be a subset of A^k+1. Then X will be called a blocker (of A^k+1) if for any element say (a₁,a₂,…,a_k,a_k+1) of A^k+1, there is some element (x₁,x₂,…,x_k,x_k+1) of X such that x_i equals a_i for at least two i. The smallest size of a blocker set X will be denoted by α(m,k)and the corresponding blocker set will be called a minimal blocker. Honsberger (who credits Schellenberg for the result) essentially proved that α(2n,2) equals 2n² for all n. Using orthogonal arrays, we obtain precise numbers α(m,k) (and lower bounds in other cases) for a large number of values of both k and m. The case k=2 that is three coordinate places (and small m) corresponds to the usual combination lock. Supposing that we have a defective combination lock with k+1 coordinate places that would open if any two coordinates are correct, the numbers α(m,k) obtained here give the smallest number of attempts that will have to be made to ensure that the lock can be opened. It is quite obvious that a trivial upper bound for α(m,k) is m² since allowing the first two coordinates to take all the possible values in A will certainly obtain a blocker set. The results in this paper essentially prove that α(m,k) is no more than about m²/k in many cases and that the upper bound cannot be improved. The paper also obtains precise values of α(m,k) whenever suitable orthogonal arrays of strength two (that is, mutually orthogonal Latin squares) exist.     

Generalized vector-valued paranormed sequence space using modulus function

In this paper we introduce a generalized vector-valued paranormed sequence space N_p(E_k,Δ^m,f,s) using modulus function f, where p=(p_k) is a bounded sequence of positive real numbers such that inf_kp_k>0,(E_k,q_k) is a sequence of seminormed spaces with E_k+1⊆E_k for each k ∈ N and s?0. We have also studied sequence space N_p(E_k,Δ^m,f^r,s), where f^r=f°f°f°,…,f (r-times composition of f with itself) and r∈N={1,2,3,…}. Results regarding completeness, K-space, normality, inclusion relations etc. are derived. Further, a study of multiplier of the set N_p(E_k,f,s) is also made by choosing (E_k,‖·‖_k) as sequence of normed algebras.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

A relation between Bernoulli numbers

We give a p-adic proof of a certain new relation between the Bernoulli numbers B_k, similar to Euler's formula Σ_k=2^m?2(_k^m)B_kB_m?k = ?(m+1)B_m, m ≥ 4.