There are no de bruijn sequences of span n with complexity 2n − 1 + n + 1

If s = (s₀, s₁,…, s_2ⁿ?1) is a binary de Bruijn sequence of span n, then it has been shown that the least length of a linear recursion that generates s, called the complexity of s and denoted by c(s), is bounded for n ? 3 by 2^{n ? 1} + n ? c(s) ? 2ⁿ ?1. A numerical study of the allowable values of c(s) for 3 ? n ? 6 found that all values in this range occurred except for 2^n?1 + n + 1. It is proven in this note that there are no de Bruijn sequences of complexity 2^n?1 + n + 1 for all n ? 3.     

On the complexities of de Bruijn sequences

The shortest linear recursion which generates a de Bruijn sequence is defined to be the complexity of the sequence. It is shown that the complexity of a binary de Bruijn sequence of span n is bounded by 2ⁿ ? 1 from above and 2^{n ? 1} + n from below. Results on the distribution of the complexities are also presented.     

Further results on correlation functions of de Bruijn sequences

In this paper we develop some bounds for the correlation functions of sequences with period 2 ⁿ and specific linear complexities. These bounds are also applicable to the correlation functions of de Bruijn sequences with spann and specific linear complexities. It is interesting that a conjecture of Chan, Games and Key's for the case ofn=2 ^m can be proved easily by using the results developed here. Their conjecture asserts that there are no de Bruijn sequences with spann and linear complexity 2 ^n–1+n+1. The comjecture was proved by Games by a different method.Institute of Systems Science, Academic Sinica     

Elliptic equation with a singular potential in a domain with a conic point

This paper deals with the behavior of the nonnegative solutions of the problem $$- \Delta u = V(x)u, \left. u \right|\partial \Omega = \varphi (x)$$ in a conical domain Ω ? ? ⁿ , n ≥ 3, where 0 ≤ V (x) ∈ L₁(Ω), 0 ≤ ?(x) ∈ L₁(?Ω) and ?(x) is continuous on the boundary ?Ω. It is proved that there exists a constant C _*(n) = (n ? 2)²/4 such that if V ₀(x) = (c + λ ₁)|x|^?2, then, for 0 ≤ c ≤ C _*(n) and V(x) ≤ V ₀(x) in the domain Ω, this problem has a nonnegative solution for any nonnegative boundary function ?(x) ∈ L ₁(?Ω); for c > C _*(n) and V(x) ≥ V ₀(x) in Ω, this problem has no nonnegative solutions if ?(x) > 0.     

An asymptotic bound for the complexity of monotone graph properties

We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ¼n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ½n(n?1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ?n ², proved in the same paper. In case that the evasiveness conjecture holds, it is ?n(n−1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) .     

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.     

The product of linear nonhomogeneous forms

We show that for an arbitrary unimodular lattice Λ of dimension n and an arbitrary point C =(c₁, c₂...c_n) ? Rⁿ a point Y = (y₁, y₂,..., y_n) ε Λ can be found and also a number h, satisfying the condition 1 ?h ? 2^?n/2 θ^?1 + 1 (0 < θ ? 2^?n/2), such that the inequality $$\prod\nolimits_{i = 1}^n {\left| {Y_i + hc_i } \right|}< \theta $$ will be satisfied.     

The genus of the symmetric quadripartite graph

In this paper the following formula for the genus of the symmetric quadripartite graph is proved. γ(K_n,n,n,n) = (n?1)² for all n≠3.     

On a generalization of Minkowski's convex body theorem

Given a lattice $\text{Λ ? R}{}^{\mathrm{n}}$ and a bounded function g(x), x ∈ Rⁿ, vanishing outside of a bounded set, the functions ?(x)$\text{g}\text{?}\text{(x)?}$max_u∈Λg(u +x), ?(x)?Σ_{u∈Λ g(u +x)}, and ?₊(x)?Σ_u∈Λ max_{v∈Λ min {g(v + x); g(u + v + x)}} are defined and periodic mod Λ on Rⁿ. In the paper we prove that ?(x) + ?₊(x) ? 2?(x) ≥ ?(x) + h?₊(x) ? 2?(x) holds for all x ∈ Rⁿ, where h(x) is any “truncation” of g by a constant c ≥ 0, i.e., any function of the form h(x)?g(x) if g(x) ≤ c and h(x)?c if g(x) > c. This inequality easily implies some known estimations in the geometry of numbers due to Rado [1] and Cassels [2]. Moreover, some sharper and more general results are also derived from it. In the paper another inequality of a similar type is also proved.     

On a property of plane curves

Let γ:[0,1]→²[0,1] be a continuous curve such that γ(0)=(0,0), γ(1)=(1,1), and γ(t)∈²(0,1) for all t∈(0,1). We prove that, for each n∈N, there exists a sequence of points Ai, 0?i?n+1, on γ such that A₀=(0,0), An+1=(1,1), and the sequences and , 0?i?n, are positive and the same up to order, where π₁, π₂ are projections on the axes.     

Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

THE EXTREME POINTS OF SEVERAL CLASSES OF ANALYTIC FUNCTIONS

1Intr0ducti0nLetAden0tethesetofallfunctionsanalyticinA={z:Izl<1}.LetB={W:WEAandIW(z)l51}.Aisalocallyconvexlineaztop0l0gicalspacewithrespecttothetopologyofuniformconvergenceon`c0mpact8ubsetsofA-LetTh(c1,'tc.-1)={p(z):p(z)EA,Rop(z)>0,p(z)=1 clz czzz ' c.-lz"-l 4z" ',wherecl,',cn-1areforedcomplexconstants}.LetTh,.(b,,-..,b,-,)={p(z):P(z)'EAwithReP(z)>Oandp(z)=1 blz ' b.-lz"-l 4z" '-,wherebl,-'-jbu-1areffeedrealconstantsanddkarerealnumbersf0rk=n,n 1,'--}-LetTu(l1,'i'tI.-1)={…     

Ruzsa’s constant on additive functions

A function f : N → R is called additive if f(mn)= f(m)+f(n)for all m, n with(m, n)= 1. Let μ(x)= max n≤x(f(n)f(n + 1))and ν(x)= max n≤x(f(n + 1)f(n)). In 1979, Ruzsa proved that there exists a constant c such that for any additive function f , μ(x)≤ cν(x 2 )+ c f , where c f is a constant depending only on f . Denote by R af the least such constant c. We call R af Ruzsa's constant on additive functions. In this paper, we prove that R af ≤ 20.     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Third order efficiency of conditional tests for exponential families

Let P_η, η = (θ, γ) ∈ Θ × Γ ? $\text{R}$ × $\text{R}$^k, be a (k + 1)-dimensional exponential family. Let $\text{?}{}_{\mathrm{n}}{}^1$, n ∈ $\text{N}$, be an optimal similar test for the hypothesis {P_(θ,γ)ⁿ: γ ∈ Γ} (θ ∈ Θ fixed) against alternatives P_(θ1,γ1)ⁿ, θ₁ > θ, γ₁ ∈ Γ. It is shown that (?_n¹)_{n∈$\text{N}$} is third order efficient in the class of all test-sequences that are asymptotically similar of level α + o(n^?1) (locally uniformly in the nuisance parameter γ).     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

On the asymptotics of the number of states for the Bose-Maslov gas

For a given sequence λ _j of positive numbers whose counting function ρ(λ) has the asymptotics ρ(λ) = c ₀ λ ^1+γ (1 + O(λ ^?? )) with γ > ?1 and ? > 0 as λ → ∞, we consider sequences {N _j } of nonnegative integers such that $\sum\limits_{j = 1}^\infty {\lambda _j N_j \leqslant E} ,$ where E > 0, and find the asymptotics as E → ∞ of the number N(E) of such sequences.     

Zero density of L-functions related to Maass forms

Let f(z) be a Hecke-Maass cusp form for SL ₂(?), and let L(s, f) be the corresponding automorphic L-function associated to f. For sufficiently large T, let N(σ, T) be the number of zeros ρ = β +iγ of L(s, f) with |γ| ? T, β ? σ, the zeros being counted according to multiplicity. In this paper, we get that for 3/4 ? σ ? 1 ? ?, there exists a constant C = C(?) such that N(σ,T) ? T ^2(1?σ)/σ(logT) ^C , which improves the previous results.     

Connectivity,genus, and the number of components in vertex-deleted subgraphs

Let c(G) denote the number of components in a graph G. It is shown that if G has genus γ and isk-connected with k ? 3, then c(G ? X) ? (2/(k ? 2))(| X | ? 2 + 2γ), for all X? V(G) with | X | ? k. Some implications of this result for planar graphs (y = 0) and toroidal graphs (y = 1) are considered.