Incomplete Character Sums and Polynomial Interpolation of the Discrete Logarithm

In the first part of the paper, certain incomplete character sums over a finite field F_p^r are considered which in the case of finite prime fields F_p are of the form ∑^A+N−1_n=Aχ(g(n))ψ(f(n)), where A and N are integers with 1≤N<p, g and f are polynomials over F_p, and χ denotes a multiplicative and ψ an additive character of F_p. Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude N^1/2p^r/4. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the finite prime field F_p for N consecutive elements of F_p must have a degree at least of the order of magnitude Np^−1/2. In this paper this result is extended to arbitrary F_p^r. The proof is based on the above new bound for incomplete hybrid character sums.     

Infinite class of new sign ambiguities

In 1934, two kinds of multiplicative relations, the norm and the Davenport-Hasse relations, between Gauss sums, were known. In 1964, H. Hasse conjectured that the norm and the Davenport-Hasse relations were the only multiplicative relations connecting Gauss sums over Fp. However, in 1966, K. Yamamoto provided a simple counterexample disproving the conjecture. This counterexample was a new type of multiplicative relation, called a sign ambiguity, involving a ± sign not connected to elementary properties of Gauss sums. In this paper, we give an explicit product formula involving Gauss sums which generates an infinite class of new sign ambiguities, and we resolve the ambiguous sign by using Stickelberger?s theorem.     

Равносходимость разложений в кратный ряд и интеграл фурье, «прямоугольные частичные суммы» которых рассматриваются по некоторой подпоследовательности

In this paper we investigate the problem of the equiconvergence on T ^N = [-π, π) ^N of the expansions in multiple trigonometric series and Fourier integral of functions f ∈ L _p (T ^N ) and g ∈ L _p (? ^N ), where p > 1, N ≥ 3, g(x) = f(x) on T ^N , in the case when the “rectangular partial sums” of the indicated expansions, i.e.,– _n (x; f) and J _α(x; g), respectively, have indices n ∈ ? ^N and α ∈ ? ^N (n _j = [α _j ], j = 1,...,N, [t] is the integer part of t ∈ ?¹), in those certain components are the elements of “lacunary sequences”.     

Arithmetic progressions in multiplicative groups of finite fields

Let G be a multiplicative subgroup of the prime field F _p of size |G| > p^1?κ and r an arbitrarily fixed positive integer. Assuming κ = κ(r) > 0 and p large enough, it is shown that any proportional subset A ? G contains non-trivial arithmetic progressions of length r. The main ingredient is the Szemerédi–Green–Tao theorem.     

Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz

Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.     

Sign or root of unity ambiguities of certain Gauss sums

Gauss sums play an important role in number theory and arithmetic geometry. The main objects of study in this paper are Gauss sums over the finite field with q elements. Recently, the problem of explicit evaluation of Gauss sums in the small index case has been studied in several papers. In the process of the evaluation, it is realized that a sign (or a root of unity) ambiguity unavoidably occurs. These papers determined the ambiguities by the congruences modulo L, where L is certain divisor of the order of Gauss sum. However, such method is unavailable in some situations. This paper presents a new method to determine the sign (root of unity) ambiguities of Gauss sums in the index 2 case and index 4 case, which is not only suitable for all the situations with q being odd, but also comparatively more efficient and uniform than the previous method.     

The push-out space of immersed spheres

Let f: M ^m → ? ^m+1 be an immersion of an orientable m-dimensional connected smooth manifold M without boundary and assume that ξ is a unit normal field for f. For a real number t the map f _tξ: M ^m → ? ^m+1 is defined as f _tξ(p) = f(p) + tξ(p). It is known that if f _tξ is an immersion, then for each p ∈ M the number of the focal points on the line segment joining f(p) to f _tξ(p) is a constant integer. This constant integer is called the index of the parallel immersion f _tξ and clearly the index lies between 0 and m. In case f: $\mathbb{S}^m \to \mathbb{R}^{m + 1} $ is an immersion, we study the presence of a component of index μ in the push-out space Ω(f). If there exists a component with index μ = m in Ω(f) then f is known to be a strictly convex embedding of $\mathbb{S}^m $ . We reveal the structure of Ω(f) when $f(\mathbb{S}^m )$ is convex and nonconvex. We also show that the presence of a component of index μ in Ω(f) enables us to construct a continuous field of tangent planes of dimension μ on $\mathbb{S}^m $ and so we see that for certain values of μ there does not exist a component of index μ in Ω(f).     

Iwasawa invariants and Kummer conguruences

Let f(x, χ) be the Iwasawa power series for the p-adic L-function L_p(s, χ), where χ is an even nonprincipal character with conductor not divisible by p² (or by 8, when p = 2). The divisibility by p of the first p coefficients of f(x, χ) is characterized by Kummer type congruences of generalized Bernoulli numbers. Applications to Iwasawa invariants and class numbers of imaginary Abelian fields are discussed.     

A note on the number of solutions of the generalized Ramanujan-Nagell equation x 2 ? D = p n

Let D be a positive integer, and let p be an odd prime with p ? D. In this paper we use a result on the rational approximation of quadratic irrationals due to M. Bauer, M.A. Bennett: Applications of the hypergeometric method to the generalized Ramanujan-Nagell equation. Ramanujan J. 6 (2002), 209–270, give a better upper bound for N(D, p), and also prove that if the equation U ² ? DV ² = ?1 has integer solutions (U, V), the least solution (u ₁, v ₁) of the equation u ² ? pv ² = 1 satisfies p ? v ₁, and D > C(p), where C(p) is an effectively computable constant only depending on p, then the equation x ² ? D = p ⁿ has at most two positive integer solutions (x, n). In particular, we have C(3) = 10⁷.     

Potential theory associated with Uhlenbeck-Ornstein process

Some parallel results of Gross' paper (Potential theory on Hilbert space, J. Functional Analysis1 (1967), 123–181) are obtained for Uhlenbeck-Ornstein process U(t) in an abstract Wiener space (H, B, i). Generalized number operator $\text{N}$ is defined by $\text{N}$f(x) = ?lim_∈←0{E[f($\text{U}$(τ^∈_ξ))] ? f(x)}/E[τ^∈_ξ, where τ_x^? is the first exit time of U(t) starting at x from the ball of radius ? with center x. It is shown that $\text{N}$f(x) = ?trace D²f(x)+〈Df(x),x〉 for a large class of functions f. Let r_t(x, dy) be the transition probabilities of U(t). The λ-potential G_λf, λ > 0, and normalized potential Rf of f are defined by G_λf(X) = ∫₀^∞e^?λtr_tf(x) dt and Rf(x) = ∫₀^∞ [r_tf(x) ? r_tf(0)] dt. It is shown that if f is a bounded Lip-1 function then trace D²G_λf(x) ? 〈DG_λf(x), x〉 = ?f(x) + λG_λf(x) and trace D²Rf(x) ? 〈DRf(x), x〉 = ?f(x) + ∫_Bf(y)p₁(dy), where p₁ is the Wiener measure in B with parameter 1. Some approximation theorems are also proved.     

The circular dimension of a graph

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a graph G, then a collection of functions {f_i}^m_n=1, each f_i mapping each vertex of V into anarc on a fixed circle, is said to define an m-arc intersection model for G if for all x,y ? V, xly ? (∨_i?m)(f_i(x)∩f_i(y)≠Ø). The circular dimension of a graph G is defined as the smallest integer m such that G has an m-arc intersection model. In this paper we establish that the maximum circular dimension of any complete partite graph having n vertices is the largest integer p such that 2^p+p?n+1.     

Approximation of bandlimited functions by trigonometric polynomials

Let σ > 0. For 1 ≦ p ≦ ∞, the Bernstein space B _σ ^p is a Banach space of all f ∈ L ^p (?) such that f is bandlimited to σ; that is, the distributional Fourier transform of f is supported in [?σ,σ]. We study the approximation of f ∈ B _σ ^p by finite trigonometric sums $$ P_\tau (x) = \chi _\tau (x) \cdot \sum\limits_{|k| \leqq \sigma \tau /\pi } {c_{k,\tau } e^{i\frac{\pi } {\tau }kx} } $$ in L ^p norm on ? as τ → ∞, where χ _τ denotes the indicator function of [?τ, τ].     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Additive properties of subgroups of finite index in fields

In this paper, we confirm a conjecture of Bergelson and Shapiro concerning subgroups of finite index in multiplicative groups of fields which have maximal additive dimension. We also show that the natural extension of subgroups Gp of prime index p inside Q^? and additive dimension p+1 to the case where p is replaced by a composite integer n leads to subgroups of bounded additive dimension on a set of positive integers n of asymptotic density 1.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

The evaluation of Gauss sums for characters of 2-power order

Let χ be a character of order 2^t on the splitting field of the polynomial x^2t−1 over the prime field with p≡3,5 (mod 8). In this paper we evaluate explicitly the Gauss sums related to the group of characters generated by χ.     

An algorithmic proof of Tutte's f-factor theorem

Let G be a multigraph on n vertices, possibly with loops. An f-factor is a subgraph of G with degree f_i at the ith vertex for i = 1, 2,…, n. Tutte's f-factor theorem is proved by providing an algorithm that either finds an f-factor or shows that it does not exist and does this in O(n³) operations. Note that the complexity bound is independent of the number of edges of G and the degrees f_i. The algorithm is easily altered to handle the problem of looking for a symmetric integral matrix with given row and column sums by assigning loops degree one. A (g,f)-factor is a subgraph of G with degree d_i at the ith vertex, where g_i ? d_i ? f_i, for i = 1,2,…, n. Lovasz's (g,f)-factor theorem is proved by providing an O(n³) algorithm to either find a (g,f)-factor or show one does not exist.     

NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

Similarity classes of3 × 3 matrices over a discrete valuation ring

Let Q be a complete discrete valuation ring. Let Π be a prime element in Q. Write P = ΠQ. For n = 1,2,…, letQ_n be the factor ring Q | Pⁿ. Let G = G1₃(Q_n. Denote by M?_n the G-module of 3 × 3 matrices over Q_n modulo scalar matrices. Canonical forms are found for every element in M?_n, and it is shown that there exist five sets of similarity classes. Some results about the general case of NxN matrices over Q also are proved.     

The Maximum Chromatic Index of Multigraphs with Given Δ and?μ

Let f(Δ,?μ) =?max {χ′(G) | Δ (G) =?Δ,?μ(G) =?μ} where χ′(G), Δ(G) and?μ(G) denote the the chromatic index, the maximum degree and the maximum multiplicity of the multigraph G, respectively. If Δ < 2μ, then Shannon’s bound implies that the gap between f(Δ,?μ) and Vizing’s bound Δ +?μ can be arbitrarily large. In this note, we prove that this is also the case for Δ ≥?2μ (see Theorem 4).