On the minimal fourier degree of symmetric Boolean functions

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f: {0, 1} ^k → {0, 1} there exists a set; \(\not 0 \ne S \subset [k]\) such that ¦S¦ = O(Γ(k)+√k, and \(\hat f(S) \ne 0\) where Γ(m)≤m ^0.525 is the largest gap between consecutive prime numbers in {1,..., m}. As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. [10]. Our bound on the degree is a significant improvement over the previous result of Kolountzakis et al. [8] who proved that ¦S¦=O(k=log k). We also show a connection between lower-bounding the degree of non-constant functions that take values in {0,1,2} and the question that we study here.     

Game saturation of intersecting families

We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = {1, 2, …, n} alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsat_F(II _n,k ) and gsat_S(II _n,k ), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^{k/3 - 5} ) \leqslant gsat_F (\mathbb{I}_{n,k} ),gsat_S (\mathbb{I}_{n,k} ) \leqslant O_k (n^{k - \sqrt {k/2} } )$ .     

On thek-stability ofm-quota games

We consider thek-stability ofm-quota games ofn players. We prove that anm-quota game (N, v), which satisfies the conditionv(S)=0 for allS, ¦S¦ ≤m ?1, is (m ?1)-stable if and only if there is no weak player. Further, some relationships between ak-stable pair and anm-quota are shown. Some ofLuce's results [1955] on Shapley quota games are generalized tom-quota games.     

Achievement and avoidance games for generating abelian groups

For any finite groupG, the DO GENERATE game is played by two players Alpha and Beta as follows. Alpha moves first and choosesx ₁ ∈G. Thek-th play consists of a choice ofx _k ∈G ?S _k ?1 whereS _n ={itx ₁,...,x _n }. LetG _n = 〈S _n 〉. The game ends whenG _n =G. The player who movesx _n wins. In the corresponding avoidance game, DON'T GENERATE, the last player to move loses. Of course neither game can end in a draw. For an arbitrary group, it is an unsolved problem to determine whether Alpha or Beta wins either game. However these two questions are answered here for abelian groups.     

Some dimensional results for homogeneous Moran sets

Let ?(¦n _k ¦k?1,¦c _k ¦k?1) be the collection of homogeneous Moran sets determined by ¦n _k ¦k?1 and ¦c _k ¦k?1, where ¦n _k ¦k?1 is a sequence of positive integers and ¦c _k ¦k?1 a sequence of positive numbers. Then the maximal and minimal values of Hausdorff dimensions for elements in ? are determined. The result is proved that for any values between the maximal and minimal values, there exists an element in ?(¦n _k ¦k?1,¦c _k¦k?1) such that its Hausdorff dimension is equal tos. The same results hold for packing dimension. In the meantime, some other properties of homogeneous Moran sets are discussed.     

On a property of the set of radiation patterns

Consider the exterior boundary value problem (▽² + K²) u = 0, in Ω, k >0. $\text{u¦}{}_{\mathrm{\Gamma }}\text{= h}$, where Γ is a smooth closed connected surface in $\text{R}$³, $\text{u ~}\text{exp}\text{(ik ¦x¦)¦x¦}{}^{\mathrm{?1}}\text{∝(k, n)}\text{as}\text{¦X¦→ ∞, n = x¦x¦}{}^{\mathrm{?1}}$, ∝ is called the radiation pattern. We prove that when h runs through any dense set in L²(Γ) the corresponding radiation pattern ∝(k,n) runs through a dense set in L²(S²) for any k >0, where S² is the unit sphere in $\text{R}$³.     

Некоторые точные инт егральные оценки про изводных рациональных и алгеб раических функций. Пр иложения

Exact estimates are obtained for integrals of absolute values of derivatives and gradients, for integral moduli of continuity and for major variations of piecewise algebraic functions (in particular, for polynomials, rational functions, splines, etc.). These results are applied to the problems of approximation theory and to the estimates of Laurent and Fourier coefficients. Typical results:

1. IfE is a measurable subset of the circle or of a line in thez-plane andR(z) is a rational function of degree ≦n, ¦R(z)¦≦ (z∈E), then ∝_E ¦R′(z)¦dz¦≦ 2πn; the latter estimate is exact forn=0, 1, ... and everyE with positive measure;
2. Iff(x ₁,x ₂, ...,x _m) is a real valued piecewise algebraic function of order (n, k) on the unit ballD?R ^m (in particular, a real valued rational function of order ≦n), and ¦f¦≦1 onD, then ∝_D¦gradf¦dx≦2π ^m/2n/Π(m/2); herem≧1, n≧0, 1≦k<∞;
3. LetE=Π={z∶¦z¦=1}, and letc _m(R) be the mth Laurent coefficient ofR onΠ,C _m(n)=sup{¦cm(R)¦}, where sup is taken over allR from 1), then 1/7 min {n/¦m¦, 1} ≦C _m(n) ≦ min {n/¦m¦, 1}.

     

Approximate solutions of functional differential equations

The author discusses the best approximate solution of the functional differential equation x′(t) = F(t, x(t), x(h(t))), 0 < t < l satisfying the initial condition x(0) = x₀, where x(t) is an n-dimensional real vector. He shows that, under certain conditions, the above initial value problem has a unique solution y(t) and a unique best approximate solution $\text{p}\text{?}{}_{\mathrm{k}}\text{(t)}$ of degree k (cf. [1]) for a given positive integer k. Furthermore, $\text{sup}{}_{\mathrm{0?t?l}}\text{¦}\text{p}\text{?}{}_{\mathrm{k}}\text{(t) ? y(t)¦ → 0}\text{as}\text{k → ∞}$, where ¦ · ¦ is any norm in Rⁿ.     

Everywhere divergent Φ-means of Fourier series

For a function ? ∈, L ¹( $\mathbb{T}$ ), we investigate the sequence (C, 1) of mean values Φ(¦S _k (x, ?) ? ?(x)¦), where Φ(t): [0, +∞) → [0,+∞), Φ(0) = 0, is a continuous increasing function. We prove that if Φ increases faster than exponentially, then these means can diverge everywhere. Divergence almost everywhere of such means was established earlier.     

A characterization of the groups L3(2n)

This note is concerned with finite groups in which a Sylow two-subgroup S has an elementary Abelian subgroup E of order 2²ⁿ, n≥2, such that E=A × z(S), ¦A¦=2ⁿ, and C_S(a)=E for any involutiona ∈ A. It is proved that a simple group satisfying this condition is isomorphic to L₃,(2ⁿ).     

On some alternative quadratic equations

From the quadratic functional equation ?(x + y) + ?(x ? y) ? 2?(x) ? 2f(y) = 0 various alternative equations are derived here by grouping in different ways its terms and then equating norms. Some equivalence results are proved in the class of functionals ?: X → (?, ¦· ¦). Suitable examples concerning operators ?: X → (E,∥· ∥) with values in normed spaces show that in this more general setting such an equivalence can fail to be true.     

A dynamic solution in N-person cooperative game theory

We formulate a cooperative game as an extended form game in which each player in turn proposes payoffs to a coalition over M steps. Payoffs at time t are discounted by a penalty function f(t). If all players in a coalition agree to their payoffs, they receive them. Under a convergence hypothesis verified by computer for three players in many cases, we compute the payoffs resulting from a coalition pattern and give necessary conditions for particular patterns. The resulting solution is related to the Nash bargaining solution and the competitive solution.     

Formulation of a Ritz-Galerkin type procedure for the approximate solution of the neutron transport equation

The one-group neutron transport equation is commonly given as an integrodifferential equation for the neutron density ψ(x, ω) over a domain G × S in the five-dimensional phase space $\text{E}{}_3\text{× S(¦ ω ¦ = 1)}$. In this paper we show how, by decomposing the domain of the transport operator into a complementary pair of manifolds by means of a projection operator, any transport problem can be formulated, on either manifold, in terms of a symmetric positive definite operator. We use Friedrichs' method to extend the operator to a selfadjoint operator and look for a generalized solution by minimizing a certain functional over the appropriate Hilbert space. A Ritz-Galerkin type approximation procedure is formulated, and an estimate for the difference between the exact and approximate solution is given. The procedure is illustrated for a special choice of finite dimensional subspace.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

Log-convexity and log-concavity of hypergeometric-like functions

We find sufficient conditions for log-convexity and log-concavity for the functions of the forms a?∑fkk(a)xk, a?∑fkΓ(a+k)xk and a?∑fkxk/k(a). The most useful examples of such functions are generalized hypergeometric functions. In particular, we generalize the Turán inequality for the confluent hypergeometric function recently proved by Barnard, Gordy and Richards and log-convexity results for the same function recently proved by Baricz. Besides, we establish a reverse inequality which complements naturally the inequality of Barnard, Gordy and Richards. Similar results are established for the Gauss and the generalized hypergeometric functions. A conjecture about monotonicity of a quotient of products of confluent hypergeometric functions is made.     

The derivation equation for C k -functions: stability and localization

For a given integer k ∈ ? we determine the possible forms of operators T: C ^k (?) → C(?) satisfying a generalized Leibniz rule operator equation T(f · g)(x) = Tf(x) · g(x)+f(x) · Tg(x)+S(f, g)(x), f,g ∈ C ^k (?), x ∈ ? for two different types of perturbations S(f, g). In the first case, S is given by a function B in localized form $$S(f,g)(x) = B(x,({f^{(j)}}(x))_{j = 0}^{k - 1},({g^{(j)}}(x))_{j = 0}^{k - 1})$$ involving only derivatives of lower order. We show that, if in addition T annihilates the polynomials of degree ≤ k ? 1, T is a multiple of the k-th derivative. For k = 2 and functions on ? ⁿ , we give a characterization of the Laplacian by a similar equation, orthogonal invariance and annihilation of affine functions. In the second setting, we assume S to have the form S(f, g)(x) = Af(x) · Ag(x) where A: C ^k (?) → C(?) is a general operator. Thus here, S has a product form, but the factor Af(x) is not assumed to depend only on the jet of f at x. We describe the possible forms of T and A satisfying the generalized Leibniz rule; T and A turn out to be closely related. Here, T and A need not to be localized, i.e., Tf(x) and Af(x) may depend on values f(y) for y ≠ x.     

Note On the core of a collection of coalitions

. For a collection Ω of subsets of a finite set N we define its core to be equal to the polyhedral cone {x∈IR ^N : ∑ _i∈N x _i =0 and ∑ _i∈S x _i ≥0 for all S∈Ω}. This note describes several applications of this concept in the field of cooperative game theory. Especially collections Ω are considered with core equal to {0}. This property of a one-point core is proved to be equivalent to the non-degeneracy and balancedness of Ω. Further, the notion of exact cover is discussed and used in a second characterization of collections Ω with core equal to {0}.     

Bounds for the spectral abscissa of an element in a Banach algebra

For an arbitrary element x with spectrum sp(x) in a Banach algebra with identity e ≠ 0 we define the upper (lower) spectral abscissa \(\mathop {\sigma + (x)}\limits_{( - )} = \mathop {\max }\limits_{(\min )} \operatorname{Re} \lambda ,\lambda \in sp(x)\) . With the aid of the spectral radius \(\rho (x) = \mathop {\max }\limits_{\lambda \in sp(x)} \left| \lambda \right| = \mathop {\lim }\limits_{n \to + \infty } \parallel x^n {{1 - } \mathord{\left/ {\vphantom {{1 - } n}} \right. \kern-0em} n}\) we prove the following bounds: γ_?(x)?σ_?(x)?Γ_?(x)?₊(x)?σ₊(x)?γ₊(x), Γ_(±)(x)=(2δ_(±))^?1 (ρ _δ ² )_(±)?δ _(±) ² ?ρ ₀ ² )(δ_(±)≠0), γ_(±)(x)= (±)ρ_δ(±)?δ_(±), δ₊?0, δ_??0 ρ _(±) ^δ = ρ(x+eδ_(±)). We mention a case where equality is achieved, some corollaries,and discuss the sharpness of the bounds: for every ? > 0 there is a δ: ¦δ¦ ≥ρ ₀ ² /2?, such that Δ: = ¦γ_(±) x?Γ_(±) x¦?ε and conversely, if the bounds are computed for some δ ≠ 0, then △ ≤ρ ₀ ² /2 ¦δ¦. An example is considered.     

Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.     

Adding machines, kneading maps, and endpoints

Given a unimodal map f, let I=[c₂,c₁] denote the core and set E={(x₀,x₁,…)∈(I,f)|xi∈ω(c,f) for all i∈N}. It is known that there exist strange adding machines embedded in symmetric tent maps f such that the collection of endpoints of (I,f) is a proper subset of E and such that limk→∞Q(k)≠∞, where Q(k) is the kneading map.We use the partition structure of an adding machine to provide a sufficient condition for x to be an endpoint of (I,f) in the case of an embedded adding machine. We then show there exist strange adding machines embedded in symmetric tent maps for which the collection of endpoints of (I,f) is precisely E. Examples of this behavior are provided where limk→∞Q(k) does and does not equal infinity, and in the case where limk→∞Q(k)=∞, the collection of endpoints of (I,f) is always E.