Local solvability of the k-Hessian equations

We give a classification of second-order polynomial solutions for the homogeneous k-Hessian equation σ_k[u] = 0. There are only two classes of polynomial solutions: One is convex polynomial; another one must not be(k + 1)-convex, and in the second case, the k-Hessian equations are uniformly elliptic with respect to that solution. Based on this classification, we obtain the existence of C∞local solution for nonhomogeneous term f without sign assumptions.     

On the proof of continued fraction expansions for irrationals

We use matrices to prove two theorems in regard to the continued fraction expansion for Σ_{k = 0}^∞u^−2k and for Σ_{k = 0}^∞u^−c(k), where c(k) is any sequence of positive integers that increase quickly.     

Polynomials arising in factoring generalized Vandermonde determinants II: A condition for monicity

In our previous paper [1], we observed that generalized Vandermonde determinants of the form V_n;ν(x₁,…,x_s) = |x_i^μk|, 1 ≤ i, k ≤ n, where the x_i are distinct points belonging to an interval [a, b] of the real line, the index n stands for the order, the sequence μ consists of ordered integers 0 ≤ μ₁ < μ₂ < … < μ_n, can be factored as a product of the classical Vandermonde determinant and a Schur function. On the other hand, we showed that when x = x_n, the resulting polynomial in x is a Schur function which can be factored as a two-factors polynomial: the first is the constant ∏_i=1ⁿ⁻¹ x_i^μ₁ times the monic polynomial ∏_i=1ⁿ⁻¹ (x − x_i, while the second is a polynomial P_M(x) of degree M = m_n−1 − n + 1. In this paper, we first present a typical application in which these factorizations arise and then we discuss a condition under which the polynomial P_M (x) is monic.     

Tension-flow polynomials on graphs

An orientation of a graph is acyclic (totally cyclic) if and only if it is a “positive orientation” of a nowhere-zero integral tension (flow). We unify the notions of tension and flow and introduce the so-called tension-flows so that every orientation of a graph is a positive orientation of a nowhere-zero integral tension-flow. Furthermore, we introduce an (integral) tension-flow polynomial, which generalizes the (integral) tension and (integral) flow polynomials. For every graph G, the tension-flow polynomial F_G(k₁,k₂) on G and the Tutte polynomial T_G(k₁,k₂) on G satisfy F_G(k₁,k₂)⩽T_G(k₁−1,k₂−1). We also characterize the graphs for which the inequality is sharp.     

Independence roots and independence fractals of certain graphs

The independence polynomial of a graph G is the polynomial ∑i _k x ^k , where i _k denote the number of independent sets of cardinality k in G. In this paper, we obtain the relationships between the independence polynomial of path P _n and cycle C _n with Jacobsthal polynomial. We find all roots of Jacobsthal polynomial. As a consequence, the roots of independence polynomial of the family {P _n } and {C _n } are real and dense in $(-\infty,-\frac{1}{4}]$ . Also we investigate the independence fractals or independence attractors of paths, cycles, wheels and certain trees.     

On the g-circulant solutions to the matrix equation Am = λJ, II

Let g and n be positive integers and let $\text{k =}\text{n(g, n)}\text{(g}{}^{\mathrm{m}}\text{, n)}$. If θ(x) is a multiple of Σ_{i = 0}^{k ? 1}xⁱ, then the g-circulant whose Hall polynomial is equal to θ(x) satisfies the matrix equation in the title. If the g-circulant whose Hall polynomial is equal to Σ_{i = 0}^{h ? 1}xⁱ satisfies the matrix equation in the title, then h is a multiple of k.     

Factoring Polynomials over Special Finite Fields

We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which Φ_k(p) is built up from small prime factors; here Φ_k denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when Φ_k(p)=p−1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; specifically, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which Φ_k(p) has a prime factor l with l≡1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.     

Finite Commutative Chain Rings

A commutative ring with identity is called a chain ring if all its ideals form a chain under inclusion. A finite chain ring, roughly speaking, is an extension over a Galois ring of characteristic pⁿusing an Eisenstein polynomial of degree k. When p∤k, such rings were classified up to isomorphism by Clark and Liang. However, relatively little is known about finite chain rings when p∣k. In this paper, we allowed p∣k. When n=2 or when p∥k but (p−1)∤k, we classified all pure finite chain rings up to isomorphism. Under the assumption that (p−1)∤k, we also determined the structures of groups of units of all finite chain rings.     

On approximation of a function and its derivatives by a polynomial and its derivatives

Let g∈C~q[-1, 1] be such that g~((k))(±1)=0 for k=0,…,q. Let P_n be an algebraic polynomialof degree at most n, such that P_n~((k))(±1)=0 for k=0,…,[_2~ (q+1)]. Then P_n and its derivativesP_n~((k)) for k≤q well approximate g and its respective derivatives, provided only that P_n well approxi-mates g itself in the weighted norm ‖g(x)-P_n(x) (1-x~2)~(1/2)~q‖This result is easily extended to an arbitrary f∈C~q[-1, 1], by subtracting from f the polynomial ofminnimal degree which interpolates f~((0))…,f~((q)) at±1. As well as providing easy criteria for judging the simultaneous approximation properties of a givenPolynomial to a given function, our results further explain the similarities and differences betweenalgebraic polynomial approximation in C~q[-1, 1] and trigonometric polynomial approximation in thespace of q times differentiable 2π-periodic functions. Our proofs are elementary and basic in character,permitting the construction of actual error estimates for simultaneous approximation proedures for smallvalues of q.     

Independence polynomials of circulants with an application to music

The independence polynomial of a graph G is the generating function I(G,x)=∑_k≥0i_kx^k, where i_k is the number of independent sets of cardinality k in G. We show that the problem of evaluating the independence polynomial of a graph at any fixed non-zero number is intractable, even when restricted to circulants. We provide a formula for the independence polynomial of a certain family of circulants, and its complement. As an application, we derive a formula for the number of chords in an n-tet musical system (one where the ratio of frequencies in a semitone is 2^1/n) without ‘close’ pitch classes.     

Complexity Estimates for the Schmüdgen Positivstellensatz

LetKbe a closed basic set inRⁿgiven by the polynomial inequalities φ₁≥ 0, . . . , φ_m≥ 0 and let Σ be the semiring generated by the φ_kand the squares inR[x₁, . . . ,x_n]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iff∈R⁺+ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0⁺, in any representation off + das an element of Σ in terms of the φ_k, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd^−1/2≤N(d) ≤Cd^−1/2log (1/d).     

Formulas for sums of powers of integers by functional equations

This paper presents a direct and simple approach to obtaining the formulas forS _k(n)= 1 ^k + 2 ^k + ... +n ^k wheren andk are nonnegative integers. A functional equation is written based on the functional properties ofS _k (n) and several methods of solution are presented. These lead to several recurrence relations for the functions and a simple one-step differential-recurrence relation from which the polynomials can easily be computed successively. Arbitrary constants which arise are (almost) the Bernoulli numbers when evaluated and identities for these modified Bernoulli numbers are obtained. The functional equation for the formulas leads to another functional equation for the generating function for these formulas and this is used to obtain the generating functions for theS _k 's and for the modified Bernoulli numbers. This leads to an explicit representation, not a recurrence relation, for the modified Bernoulli numbers which then yields an explicit formula for eachS _k not depending on the earlier ones. This functional equation approach has been and can be applied to more general types of arithmetic sequences and many other types of combinatorial functions, sequences, and problems.     

The transcendental meromorphic solutions of a certain type of nonlinear differential equations

In this paper, we study the differential equations of the following form w²+R(z)²(w(k))=Q(z), where R(z), Q(z) are nonzero rational functions. We proved the following three conclusions: (1) If either P(z) or Q(z) is a nonconstant polynomial or k is an even integer, then the differential equation w²+P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution; if P(z), Q(z) are constants and k is an odd integer, then the differential equation has only transcendental meromorphic solutions of the form f(z)=acos(bz+c). (2) If either P(z) or Q(z) is a nonconstant polynomial or k>1, then the differential equation w²+(z−z₀)P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution, furthermore the differential equation w²+A(z−z₀)²(w^′)=B, where A, B are nonzero constants, has only transcendental meromorphic solutions of the form , where a, b are constants such that Ab²=1, a²=B. (3) If the differential equation , where P is a nonconstant polynomial and Q is a nonzero rational function, has a transcendental meromorphic solution, then k is an odd integer and Q is a polynomial. Furthermore, if k=1, then Q(z)≡C (constant) and the solution is of the form f(z)=Bcosq(z), where B is a constant such that B²=C and q^′(z)=±P(z).     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Refinement of an inequality of P. L. Chebyshev

Let P _n denote the linear space of polynomials p(z:=Σ _k=0 ⁿ a _k (p)z ^k of degree ≦ n with complex coefficients and let |p|_[?1,1]: = max _x∈[?1,1]|p(x)| be the uniform norm of a polynomial p over the unit interval [?1, 1]. Let t _n ∈ P _n be the n ^th Chebyshev polynomial. The inequality $$ \frac{{\left| p \right|_{\left[ { - 1,1} \right]} }} {{\left| {a_n (p)} \right|}} \geqq \frac{{\left| {t_n } \right|_{\left[ { - 1,1} \right]} }} {{\left| {a_n (t_n )} \right|}},p \in P_n $$ due to P. L. Chebyshev can be considered as an extremal property of the Chebyshev polynomial t _n in P _n . The present note contains various extensions and improvements of the above inequality obtained by using complex analysis methods.     

On the simpleness of zeros of Stokes multipliers

The aim of this paper is to discuss the simpleness of zeros of Stokes multipliers associated with the differential equation -Φ^″(X)+W(X)Φ(X)=0, where W(X)=X^m+a₁X^m-1+?+a_m is a real monic polynomial. We show that, under a suitable hypothesis on the coefficients a_k, all the zeros of the Stokes multipliers are simple.     

Quantum Complexity of Integration

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes F^k, α_d on [0, 1]^d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(F^k, α_d, ε)≍ε^−1/γ and comp^random(F^k, α_d, ε)≍ε^−2/(1+2γ). For a quantum computer we prove comp^quant_query(F^k, α_d, ε)≍ε^−1/(1+γ) and comp^quant(F^k, α_d, ε)⩽Cε^−1/(1+γ)(log ε⁻¹)^1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove comp^coin(F^k, α_d, ε)⩽Cε^−2/(1+2γ)(log ε⁻¹)^1/(1+2γ). To summarize the results one can say that   • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small;   • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small.     

Analytical study and numerical experiments for Laplace equation with overspecified boundary conditions

In this paper, the window function, e^−αk2, is applied to regularize the divergent problem which occurs in the Laplace equation with overspecified boundary conditions in an infinite strip region. To deal with this ill-posed problem, the corner of the L-curve is chosen as the compromise point to determine the optimal α of the Gaussian window, e^−αk2, so that the high wave-number (k) content can be suppressed instead of engineering judgement using the concept of a cutoff wave-number. From the examples shown, it is found that a reasonable solution of the unknown boundary potential can be reconstructed, and that both high wave-number content and divergent results can be avoided by using the proposed regularization technique.     

Calculation of the eigenvalues of Schrödinger equations by an extension of Hill's method

The eigenfunctions of the one dimensional Schrödinger equation Ψ″ + [E ? V(x)]Ψ=0, where V(x) is a polynomial, are represented by expansions of the form $\text{∑}\text{k}\text{=0}\text{∞}{}^{\mathrm{<mtext>c</mtext>}}\text{k}{}^{\mathrm{?}}\text{k}\text{(ω,}\text{x}\text{)}$. The functions ?_k (ω, x) are chosen in such a way that recurrence relations hold for the coefficients c_k: examples treated are D_k(ωx) (Weber-Hermite functions), exp (?ωx²)x^k, exp (?cx^q)D_k(ωx). From these recurrence relations, one considers an infinite bandmatrix whose finite square sections permit to solve approximately the original eigenproblem. It is then shown how a good choice of the parameter ω may reduce dramatically the complexity of the computations, by a theoretical study of the relation holding between the error on an eigenvalue, the order of the matrix, and the value of ω. The paper contains tables with 10 significant figures of the 30 first eigenvalues corresponding to V(x) = x^2m, m = 2(1)7, and the 6 first eigenvalues corresponding to V(x) = x² + λx¹⁰ and x² + λx¹², λ = .01(.01).1(.1)1(1)10(10)100.     

The period of the Fibonacci random number generator

Smith, Green, and Klem introduced the Fibonacci RNG in [7]. A starting vector of k integers is chosen, and new numbers are generated by the recurrence r_n≡r_n−1+r_n−k (mod M). For a prime M and some choices of the parameter k, any non-zero initial vector υ gives a sequence with a period of M^kminus;1. However, in most cases, different initial values give rise to very different periods. This behavior was noted by the authors, but left unexplained. In this paper we review how sequences with short periods arise, and provide an algorithm that selects different starting vectors that give a maximal period.