Search

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

The aim of this paper is to discuss the main result in the paper by D.Y. Gao and X. Lu [On the extrema of a nonconvex functional with double-well potential in 1D, Z. Angew. Math. Phys. (2016) 67:62]. More precisely we provide a detailed study of the problem considered in that paper, pointing out the importance of the norm on the space $C^{1}[a,b]$; because no norm (topology) is mentioned on $C^{1}[a,b]$ we look at it as being a subspace of $W^{1,p}(a,b)$ for $p\in [1,\infty]$ endowed with its usual norm. We show that the objective function has not local extrema with the mentioned constraints for $p\in [1,4)$, and has (up to an additive constant) only a local maximizer for $p=\infty$, unlike the conclusion of the main result of the discussed paper where it is mentioned that there are (up to additive constants) two local minimizers and a local maximizer. We also show that the same conclusions are valid for the similar problem treated in the preprint by X. Lu and D.Y. Gao [On the extrema of a nonconvex functional with double-well potential in higher dimensions, arXiv:1607.03995]., 12 pages; in this version we added the forgotten condition $F(x) \ne 0$ for $x\in (a,b)$ on page 3

The purpose of this note is to present a new proof of a generalized form of Day's fixed point theorem. The proof we give is suggested by the work of T. Mitchell in his paper, Function algebras, means, and fixed points, [2]. The version of Day's theorem which we present here has not appeared explicitly in the literature before, and seems especially well suited for application to questions concerning fixed point properties of topological semigroups. 1. Preliminaries. We adopt the terminology and notation of [2] except where otherwise specified. New terminology will be introduced as needed. Let y be a convex compactum (compact convex set in a real locally convex linear topological space E), and let A( Y) denote the Banach space of all (real) continuous affine functions on Y under the supremum norm. Observe that A(Y) contains every function of the form h=f\Y + r where fe E* and r is real; thus A(Y) separates points of Y.

The object of this note is to point out and correct an error in the paper [21 of Fox, purporting to prove Fenchel's conjecture that a finitely generated. infinite Fuchsian group has a torsion-free normal subgroup of finite index. Fox divided the proof of the main result in his paper into four cases and an error occurs in the proofs of Cases (III) and (IV). A direct proof of Case (III) was given. While a direct proof of Case (IV) can be given, the author shows that it also follows indirectly from the result in the paper [1] of Burns and Solitar. Given any three integers a > 1, b > 1 and c > 1, there exist permutations A of order a and B of order b, such that AB has order c. Fox divided the proof of this lemma into the four cases: (I) ab 0 (mod 2) and max{a, b} ? c < a + b, (II) ab 0 (mod 2) and c : a + b, (III) a b c 1 (mod 2), (IV) a b 1 and c 0 (mod 2), and subcases. In the subcase m(a + b 2) + 2 ? c < (m + l)(b + 1) 1 of Case (III) where m is the largest integer not exceeding (c l)/(b + 1), and it is assumed that a ? b < c, the number of distinct symbols in the permutations [2, p. 64] nl~~~W B ( Wv-sI .. WI2 I7 (vWb B = (vl * *t*v W_ ***W P2) * (V W2 .. * ]Pi+]1)'

In [4], Phelps showed that in certain function algebras the unit ball is the closed convex hull of its extreme points. The algebra, C(X), of complex valued continuous functions on a compact Hausdorff space, will always have this property. The class of logmodular algebras which have a Gleason part which is total also was shown to have the property. In this paper we give an elementary proof of the first result (a proof which is, in theory at least, constructive). The simplest nontrivial example of a logmodular algebra with a total part is the disk algebra (i.e. the functions continuous on the closed disk and analytic in the interior). For this algebra we show that the extreme points (in fact the exposed points) of the unit ball form a dense subset of the boundary of the unit ball. Let U be the unit ball of C(X). It is well known that q in U is an extreme point of U if I q(x) I = 1 for all x in X. Now if f in U never vanishes, then f is in the closed convex hull of the extreme points; in factf is between two uniquely determined extreme points. We need only observe that for each x in X,f(x) is halfway between two uniquely determined extreme points of the disk and that these points vary continuously with x. Now it is not necessarily the case that each function in U can be approximated by a nonvanishing function. For a counterexample we need only look at h(z) = z in the algebra of continuous functions on the disk. (If If(z)-zj 1/e. Letfi, i = 1, *, N be the retract maps obtained from these rotations. Then I 1/N Efi(z)-z

This note deals with the correction of a small flaw in the proof of a theorem (and a lemma) in [2]. Also a simpler proof of the theorem in question is given. In the proof of Theorem 2.3 in [2], the statement "that distinct L's cannot belong to a common pure subgroup HL follows immediately from the fact that no two L's generate with G [p] the same subgroup of G" is false as it stands. One has to exercise a little more care in the selection of HL. For example, since the union [xa, Xa]aEA of all the L's (in Lemma 2.1 in [2]) is still linearly independent, there exists according to [1] a pure subgroup H of G supported by S such that HDL for each L. Hence one could choose HL=H for each L. However, all goes well if HL is chosen such that HLn [Xa, XTg aEA =L, as can easily be done. Similar remarks hold for Lemma 3.8 in [2]. A short alternate proof of Theorem 2.3 in [2] is given. In what follows let c be the cardinality of the continuum and Q be the first ordinal whose cardinality is c. The notation and terminology will be the same as that in [2].

In [2], Tosiro Tsuzzuku gave a proof of the following:THEOREM. Let G be a doubly transitive permutation group of degree n, let K be any commutative ring with unit element and let p be the natural representation of G by n × n permutation matrices with elements 0, 1 in K. Then ρ is decomposable as a matrix representation over K if and only ifn is an invertible element of K.For G the symmetric group this result follows from Theorems (2.1) and (4.12) of [1]. The proof given by Tsuzuku is unsatisfactory, although it is perfectly valid when K is a field. The purpose of this note is to give a correct proof of the general case.

M. Rosenblum in [2] presented a most ingenious proof of the Fuglede and Putnam Theorems by means of entire vector valued functions [1, p. 59]. We will demonstrate that some curious properties of bounded Hilbert space operators can be derived from Rosenblum's argument and similar arguments. Throughout this text we mean by an "operator" a bounded linear transformation of a Hilbert space into itself. Given an operator A we mean by "exp A " the uniform limit of the series I+A +A 2/2 1 +A3/3! +A4/4! + * * * . We let A * denote the adjoint of the operator A, and let z* denote the complex conjugate of the complex number z. A "normal" operator is an operator which commutes with its adjoint. A critical fact in the Rosenblum proof is that given a normal operator A and any complex number z, exp (izA) exp (iz*A *) exp (izA +iz*A *) = exp (iz*A *) exp (izA), and this operator is unitary because i(zA +z*A *) is skew hermitian. Our first result states, among other things, that the converse is true; if the above equations hold for a fixed operator A and all complex numbers z, then A is normal.

A subset A of a topological space is said to be semi-open if there exists an open set U such that U C A C Cl(U) where Cl(U) denotes the closure of U. The class of semi-open sets of a given topological space (X, J) is denoted S.O. (X, J). In the paper Semi-open sets and semi-continuity in topological spaces, Amer. Math. Monthly 70 (1963), 36-41, Norman Levine states in Theorem 10 that if J and V* are two topologies for a set X such that S.O.(X, 3) C S.O.(X, J*), then 'J C P. In a corollary to this theorem, Levine states that if S.O.(X, if) = S.O.(X,Jf*), then _T= f*. An example is given which shows the above-mentioned theorem and its corollary are false. This paper shows how different topologies on a set which determine the same class of semi-open subse,ts can arise from functions, and points out some of the implications of two topologies being related in this manner. In [6] Norman Levine defines a set A in a topological space X to be semi-open if there exists an open set U such that U C A C Cl (U), where Cl(U) denotes the closure of U. The class of semi-open sets for a given topological space (X, i) is denoted S.O. (X, sT). Levine states in Theorem 10 of [6] that if Jf and * are two topologies for a set X such that S.O. (X, i) C S.O. (X, J9 then iT C *. In a corollary to this theorem, Levine states that if S.O. (X, ) = S.O. (X, iT*), then Jf = -" The following example which is due to S. Gene Crossley and S. K. Hildebrand [1, Example 1.1] shows the above-mentioned theorem and its corollary are false. Example. Let X = la, b, cl, J; = t0, sal, la, bl, la, cl, XI, ;* = 10, sal, la, bl, XI. An exhaustion of all possibilities shows that S.O. (X, ) = S.O. (x, 5j*). Crossley and Hildebrand [3] defined two topologies iT and T* on a set X to be semi-correspondent if S.O. (X, J) = S.O. (X, 5f*). It is shown in [3] that semi-correspondence is an equivalence relation on the collection of Received by the editors March 3, 1974. AMS (MOS) subject classifications (1970). Primary 54B99; Secondary 54C10.

IN this paper Haldane points out (p. 142) a difference between his results for the mean and variance of x2 in a 2 x n-fold contingency table when the expectation p is fixed and the results obtained by me in my paper (Annals of Eugenics, Vol. VII, part III, p. 211). The difference is that I have (n 1) throughout where Haldane has n. Haldane writes, "my own results would appear to be slightly more accurate than Cochran's", which might, I think, give the impression that both Haldane's results and mine are only approximations. In fact, both results are mathematically exact, the difference between them being one of definition of x2. My paper is almost entirely concerned with the distribution of x2 when the expectation p is not known. In the results which I gave for the distribution of x2 when p is known, I retained the term S (x -x-)2 in the numerator of x2 instead of S (x np)2, to facilitate comparison between this and my other results. Thus my x2 has (n 1) degrees of freedom, whereas Haldane's x2 has n degrees of freedom. Unfortunately I did not emphasize this point in the passage concerned, and as it may have appeared misleading to others besides Haldane, I welcome this opportunity of drawing attention to it. Haldane's x2 is, of course, the one which is normally appropriate in testing the departure from independence when the expectation is known.

1. Denote by G the group of the equation upon which depends the determi. nation of the curves of order n 3 having simple contact at 1 n ( n -3 ) points with a given curve C of order n having no double points. The case in which n is odd was discussed in the former paper (Transactions, January, 1902) and G was shown to be a subgroup of the group defined by the invariants 43, 04, , , * *, the latter group being holoedrically isomorphic with the first hypoabelian grouip on 2p indices with coefficients taken modulo 2. For n even, G is contained in the group H defined by the invariants 04' 069 * with even subscripts. JORDAN has shown (Traite, pp. 229-242) that H is holoedrically isomorphic with the abelian linear group A on 2p indices with coefficients taken modulo 2. The object of the present paper is to establish the latter theorem by a short, elementary proof, which makes no use of the abstract substitutions [al, 1 ., p, p1] of JORDAN, and which exhibits explicitly the correspondence t between the substitutions of the isomorphic groups.

F(k) ={xkj x F}; F,=F; Fk= (Fk_l,F). Let (u, v, 0)=u, (u, v, 1)=(u, v), (u, v, n)=((u, v, n-1), v). Then Sanov [3] proved that (1. 1) (u, v, apa _1) p-a E F(p#)Fapa+?, /3 a = 1, 2, where p is a prime. In this paper, (1.1) is proved for the cases a= 1, 2; 3 arbitrary. A slight generalization of these results is also proved. Sanov's proof involved an investigation of ideals in a Lie Ring. In this paper, Hall's Collection Process will be used. The method also yields other formulas, e.g. (1.2) (u, v, p2 1)P' (E F2p2_pF(p) (1.3) (u, v, pa+l 1)p~l C F2pa+l paF(pl), a = 1 2, and can be used to produce numerous formulas of a similar nature. The author hopes that some of these formulas and/or the method may be of use in solving other group-theoretic problems. The author was unable to use the method to prove (1.1) for a =3. Note that for a=f = 1, (1. 1) becomes (1.4) (U, v, p 1) E F(p)Fv+1. (1.4) plays an important role in the theory of the Restricted Burnside Problem.

In the paper with the above title, which appeared in these T r a n s a c t i on s, vol. 2 (1901), p. 428, I obtained a number of general theorems concerning the zeros of functions of the form 02 y' ol y, where y is a solution of a hornogeneous linear differelntial equation of the second order. There s a further general theorem of the same character which I should have included in that paper if I had discovered it at the time, and which I now give as VII' below, it being a counterpart to VII in the earlier paper. I also give three special applications of this general result, numbered VIII', VIII", VIII"', since they are counterparts of VIII. A part of VIII' was obtained by Fite in the Annals of M athematics for June, 1917, (see the closing lines of his article) by another method; and it was this special result of Fite's that suggested to me the much more general Theorem VII'. What follows should be regarded as an addendum to the former paper, to be inserted on page 434 at the end of ? 2. All references are to that paper, to which the reader should turn for an explanation of the notation and a statement of the restrictions placed on the functions. VII'. If none of the six functions

If BP denotes the space of smooth alternating p-forms on the C' manifold M, we are interested in finding the spaces of R-linear maps from iPP to be that commute with the diffeomorphisms of M. For a compact manifold M these spaces were found by R. S. Palais. In this note we find them for noncompact M. Let V, W be the spaces of sections of two tensor bundles over a connected Coo manifold M of dimension n. In a paper [3] appearing in Trans. Amer. Math. Soc. 92 (1959), R. S. Palais studied a number of the spaces 4 (V, W) of the R-linear maps V->W natural with respect to the action on V and W of the group G of diffeomorphisms on M. We sketch the definition of this action: If g-G we define R,:F(TM) -4F(TM) to be the differential of g, and Rg:r(T*M)-->F(T*M) to be the dual of the differential of g-1. For the other spaces of tensor fields Rg is defined as the obvious tensor product of these two R-linear isomorphisms. A map c: V->W is then called natural if cRg =R,c for all g G. Palais was particularly interested in the case when V and W are the space IP of p-forms and the space bq of q-forms respectively, 0 < p, q

The first part of the theorem of the above paper states that if ois a closed convex set in real X1 ... Xn-space which is invariant under permutations of coordinates, and if C(o-) denotes the set of real symmetric nXn matrices whose eigenvalues X1, X. form the coordinates of points in a, then C(o) is convex. I am obliged to Professor R. T. Rockafellar for pointing out that this statement is essentially contained in a theorem of Chandler Davis.2 The statement also follows from an earlier result of V. B. Lidskii,3 which was not known to me at the time of publication.

Walsh's Theorem II states that if the roots of f (z) are in the circular region C, and if z is exterior to C, then ai lies in C. This is precisely the result obtained by Laguerre as given on page 59 of volume I of his collected works, if expressed in non-homogeneous coordinates as on page 57. We shall use another form of Laguerre's Theorem (loc. cit., p. 57) to prove the underlying proposition on which Walsh bases his proof of his Theorem I, as follows: Every circle through any point z and its "derived point" a as defined by (1) either passes through all the roots off ( z ), or else has at least one root in the region interior to it, and at least one root in the exterior region. I have recently called attentiont to the fact that this is a corollary of a theorem of Bocher's on jacobians which has served as a starting point in Walsh's earlier papers. With a slight change in Walsh's notation, whereby we substitute z's for a's, the proposition from which Theorem I is deduced may be stated thus

This paper contains a number of disturbing misprints: Equation (2) p. 560 should read Gpf(x) = aoxPfm+ a1xPf11 + *** + amixpf + amx. Line 17 p. 561 read Ap(x) XBp(x) instead of Ap(x)Bp(x). The term perfect (volkommen) in Theorem 1 is used in the sense of Steinitz, Algebraische Theorie der Korper, edited by Hasse and Baer, pp. 50-51. Line 21 p. 562 should read Fp(x) = Qp(x) X (xP ax) + Ax. Equation (9) p. 562 should read A = aoa(Pm-l)/(P-1) + aia(P'1)/(P-1) + + am,2a0P+1 + am-,a + am. In the expression line 9 p. 563 the last term should be A(")x. Equation (17) p. 564 should read F'"(x) = Fnl(x)P -Fn-1(Wn)PFn-1(X). Line 8 from below p. 574 should read

Among other results, it is proved that if a sequence {t 1l) of regular measures on a Hausdorff space, with values in a normed group, is convergent to zero for all a-compact sets or all open sets, then there exists a maximal open set U such that ft,1 ( U) O-* { f t,) being the associated submeasures. In [5], J. D. Stein, Jr. considers some versions of Phillip's lemma and the Vitali-Hahn-Saks theorem for sequences of regular scalar-valued Borel measures on Hausdorff spaces. The measures he considers are bounded, regular, and finitely additive Borel measures which are easily seen to be countably additive (to prove this, first note that I pi, the variation of such a measure /L, is regular, bounded, and finitely additive [5, Lemma 1]) and so for a sequence {Bi) of Borel sets, B1j0, and > 0, C a sequence of compact sets (Ki), Ki c Bi and vi(Bi \ K1) some no and so I til(BiWO), an observation which enables one to prove his results easily, in more general forms, and under weaker conditions. Theory of submeasures developed in [1] will be used. Let G be an Abelian Hausdorff topological group, X a Hausdorff topological space, and yt a countably additive, regular, G-valued measure on X (by regularity we mean that for any Borel set B in X and a 0-nbd U in G, there exists a compact set C c B such that tt(K) C U, VK c B \ C, K Borel). If G is normed [1, p. 270], we have an associated submeasure ft, AK(B) = sup{14(A)I:A c B,A Borel) = sup{ I(C)I: C c B, Ccompact), which is finite [1, p. 279, Corollary 4.1 1], exhaustive, a-subadditive, and order-continuous [1, II]. It is also regular in the sense that given E > 0 and a Borel set B, 3 a compact set K c B such that i(B \ K) < (proof by contradiction, using exhaustivity). For a collection of measures or subReceived by the editors August 25, 1976. AMS (MOS) subject classifications (1970). Primary 28A25; Secondary 46G10.

C. Hobby and C. R. B. Wright [2] have just published the following Theorem A. However, their proof seems to contain an error.2 The notation of [2] is used except that G. is not reserved for the nth term of the lower central series of G: +/(G) denotes the Frattini subgroup of G; (G, H) means the group generated by the commutators g-lh-1gh where gEG, hEH; (A1, A2, * * *, A.+,) is defined inductively as ((A1, A2, . , A.), A.+,); HCG means that H is properly included in G.

PROOF. By a theorem of Rudin a function gEH' in U whose boundary values are real a.e. on I can be analytically continued to D [3, p. 59]. The lemma follows on applying Rudin's result to gi= (1/2) (fl+f2) and g2=(i/2) (fi-f2). PROOF OF THEOREM 1. By a well-known decomposition theorem [2, p. 87], f(z)=B(z)F2(Z), where B(z) is a Blaschke product and F(z) EH1. Since the boundary values of B (z) have absolute value one a.e. on K, we have a.e. on I, f(ei0)= |f(eio)I, or B(ei0)F2(ei0) = F2(ei0) |, and hence

In this short paper we establish a (non-trivial) lower bound on the degree two entry h 2 of a Gorenstein h-vector of any given socle degree e and any codimension r. In particular, when e = 4, that is, for Gorenstein h-vectors of the form h = (1, r, h 2 , r, 1), our lower bound allows us to prove a conjecture of Stanley on the order of magnitude of the minimum value, say f(r), that h 2 may assume. In fact, we show that limr→∞ f(r) r 2/3 =6 2/3 . In general, we wonder whether our lower bound is sharp for all integers e > 4 and r > 2.

Submitted by Vitor Silverio Rodrigues (vitorsrodrigues@reitoria.unesp.br) on 2014-05-27T11:25:28Z No. of bitstreams: 0Bitstream added on 2014-05-27T14:41:41Z : No. of bitstreams: 1 2-s2.0-79951846250.pdf: 494002 bytes, checksum: 56b6ee8beddda3e7dae971355d44a19f (MD5) Made available in DSpace on 2014-05-27T11:25:28Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-03-01 Item merged in doublecheck by Felipe Arakaki (arakaki@reitoria.unesp.br) on 2015-12-11T17:28:11Z Item was identical to item(s): 71803, 21370 at handle(s): http://hdl.handle.net/11449/72321, http://hdl.handle.net/11449/21804 Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) The simplest necessary conditions for an entire function ψ(x) =∞ ∑ k=0 γk xk/k! to be in the Laguerre-Pólya class are the Turán inequalities γ2 k- γk+1γk-1 ≥ 0. These are in fact necessary and sufficient conditions for the second degree generalized Jensen polynomials associated with ψ to be hyperbolic. The higher order Turán inequalities 4(γ2 n - γn-1γn+1)(γ2n +1 - γnγn+2) - (γnγn+1 - γn-1γn+2) 2 ≥ 0 are also necessary conditions for a function of the above form to belong to the Laguerre-Pólya class. In fact, these two sets of inequalities guarantee that the third degree generalized Jensen polynomials are hyperbolic. Pólya conjectured in 1927 and Csordas, Norfolk and Varga proved in 1986 that the Turán inequalities hold for the coefficients of the Riemann ψ-function. In this short paper, we prove that the higher order Turán inequalities also hold for the ψ-function, establishing the hyperbolicity of the associated generalized Jensen polynomials of degree three. © 2010 American Mathematical Society. Departamento de Ciências de Computação e Estatística IBILCE, Universidade Estadual Paulista, 15054-000 São José do Rio Preto, SP Departamento de matemática Aplicada IMECC UNICAMP, 13083-859 Campinas, SP Departamento de Ciências de Computação e Estatística IBILCE, Universidade Estadual Paulista, 15054-000 São José do Rio Preto, SP FAPESP: 03/01874-2 FAPESP: 06/60420-0 CNPq: 305622/2009-9 CAPES: DGU-160

Let p p be an odd prime. h 1 ( p ) {h_1}(p) is the first factor of the class number of field Q ( ζ p ) Q({\zeta _p}) . We proved that \[ h 1 ( p ) ⩽ { 2 p ( p − 1 8 ( 2 l / 2 + 1 ) 4 / l ) ( p − 1 ) / 4 , if l is even, 2 p ( p − 1 8 ( 2 l − 1 ) 2 / l ) ( p − 1 ) / 4 , if l is odd . {h_1}(p) \leqslant \left \{ \begin {gathered} 2p{\left ( {\frac {{p - 1}} {{8{{({2^{l/2}} + 1)}^{4/l}}}}} \right )^{(p - 1)/4}},\quad {\text {if }}l\;{\text {is even,}} \hfill \\ 2p{\left ( {\frac {{p - 1}} {{8{{({2^l} - 1)}^{2/l}}}}} \right )^{(p - 1)/4}},\quad {\text {if }}l\;{\text {is odd}}{\text {.}} \hfill \\ \end {gathered} \right . \] From that we obtain h 1 ( p ) ⩽ 2 p ( ( p − 1 ) / 31.997158 … ) ( p − 1 ) / 4 {h_1}(p) \leqslant 2p{((p - 1)/31.997158 \ldots )^{(p - 1)/4}} which is better than Carlitz’s and Metsänkyla’s results. For the fields Q ( ζ 2 n ) Q({\zeta _{{2^n}}}) and Q ( ζ p n ) ( n ⩾ 2 ) Q({\zeta _{{p^n}}})(n \geqslant 2) , we get the similar results.

The paper is devoted to coverings by translative homothets and illuminations of convex bodies. For a given positive number $\alpha$ and a convex body $B$, $g_{\alpha}(B)$ is the infimum of $\alpha$-powers of finitely many homothety coefficients less than 1 such that there is a covering of $B$ by translative homothets with these coefficients. $h_{\alpha}(B)$ is the minimal number of directions such that the boundary of $B$ can be illuminated by this number of directions except for a subset whose Hausdorff dimension is less than $\alpha$. In this paper, we prove that $g_{\alpha}(B)\leq h_{\alpha}(B)$, find upper and lower bounds for both numbers, and discuss several general conjectures. In particular, we show that $h_{\alpha} (B) > 2^{d-\alpha}$ for almost all $\alpha$ and $d$ when $B$ is the $d$-dimensional cube, thus disproving the conjecture from Research Problems in Discrete Geometry by Brass, Moser, and Pach.

In 1993, Shub and Smale posed the problem of finding a sequence of univariate polynomials of degree $N$ with condition number bounded above by $N$. In a previous paper by C. Belt\'an, U. Etayo, J. Marzo and J. Ortega-Cerd\`a, it was proved that the optimal value of the condition number is of the form $O(\sqrt{N})$, and the sequence demanded by Shub and Smale was described by a closed formula (for large enough $N\geqslant N_0$ with $N_0$ unknown) and by a search algorithm for the rest of the cases. In this paper we find concrete estimates for the constant hidden in the $O(\sqrt{N})$ term and we describe a simple formula for a sequence of polynomials whose condition number is at most $N$, valid for all $N=4M^2$, with $M$ a positive integer., Comment: 21 pages

This paper deals with a class of singular problems involving the fractional $$p(x,\cdot )$$ -Laplace operator of the form $$\begin{aligned} \left\{ \begin{array}{ll} (-\Delta )^{s}_{p(x,\cdot )}u(x)= \frac{\lambda }{u^{\gamma (x)}}+u^{q(x)-1} &{} \hbox {in }\Omega , \\ u>0, \;\;\text {in}\;\; \Omega &{} \hbox {} \\ u=0 \;\;\text {on}\;\;{\mathbb {R}}^N\setminus \Omega , &{} \hbox {} \end{array} \right. \end{aligned}$$ where $$\Omega $$ is a smooth bounded domain in $${\mathbb {R}}^N$$ ( $$N\ge 3$$ ), $$00$$ small enough. To our best knowledge, this paper is one of the first attempts in the study of singular problems involving fractional $$p(x,\cdot )$$ -Laplace operators.

In this paper, we study a problem posed by Furstenberg on intersections between × 2 , × 3 \times 2, \times 3 invariant sets. We present here a direct geometrical counting argument to revisit a theorem of Wu and Shmerkin. This argument can be used to obtain further improvements. For example, we show that if A 2 , A 3 ⊂ [ 0 , 1 ] A_2,A_3\subset [0,1] are closed and × 2 , × 3 \times 2, \times 3 invariant respectively, assuming that dim ⁡ A 2 + dim ⁡ A 3 > 1 \dim A_2+\dim A_3>1 then A 2 ∩ ( u A 3 + v ) A_2\cap (uA_3+v) is sparse (defined in this paper) and has box dimension zero uniformly with respect to the real parameters u , v u,v such that u u and u − 1 u^{-1} are both bounded away from 0 0 .

In a little-known paper Hurwitz gave an infinite series representation of the class number for positive definite binary quadratic forms. In this paper we give a similar formula in the indefinite case. We also give a simple proof of Hurwitz's formula and indicate some extensions., Journal of the European Mathematical Society, 23 (12), ISSN:1435-9855, ISSN:1435-9863

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model $G(2n,p,q)$, which is a random graph consisting of two distinct Erdős-Renyi graphs $G(n,p)$ joined by random edges with density $q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and $r=q/p$ is a constant, we show that there is a phase transition in $r$ with threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and $r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion configuration with a bias of $\Omega(n)$. By contrast, if $r r^*$, we show that, for any initial opinion configuration, the process reaches consensus within $O(\log n)$ steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

In 1980, Onishchik introduced the index of a Riemannian symmetric space as the minimal codimension of a (proper) totally geodesic submanifold. He calculated the index for symmetric spaces of rank less than or equal to 2, but for higher rank it was unclear how to tackle the problem. In earlier papers we developed several approaches to this problem, which allowed us to calculate the index for many symmetric spaces. Our systematic approach led to a conjecture for how to calculate the index. The purpose of this paper is to verify the conjecture., 33 pages; Table 1 corrected; to appear in Journal fuer die Reine und Angewandte Mathematik

The classical Morse–Sard theorem claims that for a mapping v : R n → R m + 1 of class C k the measure of critical values v ( Z v , m ) is zero under condition k ≥ n − m . Here the critical set, or m-critical set is defined as Z v , m = { x ∈ R n : rank ∇ v ( x ) ≤ m } . Further Dubovitskiĭ in 1957 and independently Federer and Dubovitskiĭ in 1967 found some elegant extensions of this theorem to the case of other (e.g., lower) smoothness assumptions. They also established the sharpness of their results within the C k category. Here we formulate and prove a bridge theorem that includes all the above results as particular cases: namely, if a function v : R n → R d belongs to the Holder class C k , α , 0 ≤ α ≤ 1 , then for every q > m the identity H μ ( Z v , m ∩ v − 1 ( y ) ) = 0 holds for H q -almost all y ∈ R d , where μ = n − m − ( k + α ) ( q − m ) . Intuitively, the sense of this bridge theorem is very close to Heisenberg's uncertainty principle in theoretical physics: the more precise is the information we receive on measure of the image of the critical set, the less precisely the preimages are described, and vice versa. The result is new even for the classical C k -case (when α = 0 ); similar result is established for the Sobolev classes of mappings W p k ( R n , R d ) with minimal integrability assumptions p = max ⁡ ( 1 , n / k ) , i.e., it guarantees in general only the continuity (not everywhere differentiability) of a mapping. However, using some N-properties for Sobolev mappings, established in our previous paper, we obtained that the sets of nondifferentiability points of Sobolev mappings are fortunately negligible in the above bridge theorem. We cover also the case of fractional Sobolev spaces. The proofs of the most results are based on our previous joint papers with J. Bourgain and J. Kristensen (2013, 2015). We also crucially use very deep Y. Yomdin's entropy estimates of near critical values for polynomials (based on algebraic geometry tools).

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by $7$. Furthermore, we prove that every subcubic triangle-free outerplanar graph has a $(1,2,2,2)$-packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a $(1,2,2,2)$-packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a $(1,2,2,3)$-packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an $S$-packing coloring for $S=(1,3,\ldots,3)$, where $3$ appears $\Delta$ times ($\Delta$ being the maximum degree of vertices), and this property does not hold if one of the integers $3$ is replaced by $4$ in the sequence $S$., Comment: 24 pages

Let $\unicode[STIX]{x1D703}$ be an irrational real number. The map $T_{\unicode[STIX]{x1D703}}:y\mapsto (y+\unicode[STIX]{x1D703})\!\hspace{0.6em}{\rm mod}\hspace{0.2em}1$ from the unit interval $\mathbf{I}= [\!0,1\![$ (endowed with the Lebesgue measure) to itself is ergodic. In a short paper [Parry, Automorphisms of the Bernoulli endomorphism and a class of skew-products. Ergod. Th. & Dynam. Sys.16 (1996), 519–529] published in 1996, Parry provided an explicit isomorphism between the measure-preserving map $[T_{\unicode[STIX]{x1D703}},\text{Id}]$ and the unilateral dyadic Bernoulli shift when $\unicode[STIX]{x1D703}$ is extremely well approximated by the rational numbers, namely, if $$\begin{eqnarray}\inf _{q\geq 1}q^{4}4^{q^{2}}~\text{dist}(\unicode[STIX]{x1D703},q^{-1}\mathbb{Z})=0.\end{eqnarray}$$ A few years later, Hoffman and Rudolph [Uniform endomorphisms which are isomorphic to a Bernoulli shift. Ann. of Math. (2)156 (2002), 79–101] showed that for every irrational number, the measure-preserving map $[T_{\unicode[STIX]{x1D703}},\text{Id}]$ is isomorphic to the unilateral dyadic Bernoulli shift. Their proof is not constructive. In the present paper, we relax notably Parry’s condition on $\unicode[STIX]{x1D703}$: the explicit map provided by Parry’s method is an isomorphism between the map $[T_{\unicode[STIX]{x1D703}},\text{Id}]$ and the unilateral dyadic Bernoulli shift whenever $$\begin{eqnarray}\inf _{q\geq 1}q^{4}~\text{dist}(\unicode[STIX]{x1D703},q^{-1}\mathbb{Z})=0.\end{eqnarray}$$ This condition can be relaxed again into $$\begin{eqnarray}\inf _{n\geq 1}q_{n}^{3}~(a_{1}+\cdots +a_{n})~|q_{n}\unicode[STIX]{x1D703}-p_{n}| where $[0;a_{1},a_{2},\ldots ]$ is the continued fraction expansion and $(p_{n}/q_{n})_{n\geq 0}$ the sequence of convergents of $\Vert \unicode[STIX]{x1D703}\Vert :=\text{dist}(\unicode[STIX]{x1D703},\mathbb{Z})$. Whether Parry’s map is an isomorphism for every $\unicode[STIX]{x1D703}$ or not is still an open question, although we expect a positive answer.

A graph Γ is called a bi-circulant if it admits a cyclic group as a group of automorphisms acting semiregularly on the vertices of Γ with two orbits. The characterization of tetravalent edgetransitive bi-circulants was given in several recent papers. In this paper, a classification is given of connected tetravalent vertex-transitive bi-circulants of order twice an odd integer.

In this paper we study the b b -ary expansions of the square roots of the function defined by the recurrence f b ( n ) = b f b ( n − 1 ) + n f_b(n)=b f_b(n-1)+n with initial value f ( 0 ) = 0 f(0)=0 taken at odd positive integers n n , of which the special case b = 10 b=10 is often referred to as the “schizophrenic” or “mock-rational” numbers. Defined by Darling in 2004 2004 and studied in more detail by Brown in 2009 2009 , these irrational numbers have the peculiarity of containing long strings of repeating digits within their decimal expansion. The main contribution of this paper is the extension of schizophrenic numbers to all integer bases b ≥ 2 b\geq 2 by formally defining the schizophrenic pattern present in the b b -ary expansion of these numbers and the study of the lengths of the non-repeating and repeating digit sequences that appear within.

In this paper we show how to explicitly write down equations of hyperelliptic curves over Q such that for all odd primes l the image of the mod l Galois representation is the general symplectic group. The proof relies on understanding the action of inertia groups on the l-torsion of the Jacobian, including at primes where the Jacobian has non-semistable reduction. We also give a framework for systematically dealing with primitivity of symplectic mod l Galois representations. The main result of the paper is the following. Suppose n=2g+2 is an even integer that can be written as a sum of two primes in two different ways, with none of the primes being the largest primes less than n (this hypothesis appears to hold for all g different from 0,1,2,3,4,5,7 and 13). Then there is an explicit integer N and an explicit monic polynomial $f_0(x)\in \mathbb{Z}[x]$ of degree n, such that the Jacobian $J$ of every curve of the form $y^2=f(x)$ has $Gal(\mathbb{Q}(J[l])/\mathbb{Q})\cong GSp_{2g}(\mathbb{F}_l)$ for all odd primes l and $Gal(\mathbb{Q}(J[2])/\mathbb{Q})\cong S_{2g+2}$, whenever $f(x)\in\mathbb{Z}[x]$ is monic with $f(x)\equiv f_0(x) \bmod{N}$ and with no roots of multiplicity greater than $2$ in $\overline{\mathbb{F}}_p$ for any p not dividing N., Comment: 24 pages, minor corrections

In this paper, we will establish a formula that relates the product $$\prod _{\omega ^n=1} {\omega x-1 \atopwithdelims ()p-1}$$ to generalized and homogeneous multiple harmonic sums, this would allow us to derive new identities and congruences. The congruences considered in this paper are congruences in $$\mathbb {C}_p$$ which are also valid in $$\mathbb {Z}_p$$ and $$\mathbb {Z}$$ . In order to prove these congruences, we employ well-known theorems for symmetric functions and harmonic numbers.

Let $L$ be a fixed branch -- that is, an irreducible germ of curve -- on a normal surface singularity $X$. If $A,B$ are two other branches, define $u_L(A,B) := \dfrac{(L \cdot A) \: (L \cdot B)}{A \cdot B}$, where $A \cdot B$ denotes the intersection number of $A$ and $B$. Call $X$ arborescent if all the dual graphs of its resolutions are trees. In a previous paper, the first three authors extended a 1985 theorem of P{\l}oski by proving that whenever $X$ is arborescent, the function $u_L$ is an ultrametric on the set of branches on $X$ different from $L$. In the present paper we prove that, conversely, if $u_L$ is an ultrametric, then $X$ is arborescent. We also show that for any normal surface singularity, one may find arbitrarily large sets of branches on $X$, characterized uniquely in terms of the topology of the resolutions of their sum, in restriction to which $u_L$ is still an ultrametric. Moreover, we describe the associated tree in terms of the dual graphs of such resolutions. Then we extend our setting by allowing $L$ to be an arbitrary semivaluation on $X$ and by defining $u_L$ on a suitable space of semivaluations. We prove that any such function is again an ultrametric if and only if $X$ is arborescent, and without any restriction on $X$ we exhibit special subspaces of the space of semivaluations in restriction to which $u_L$ is still an ultrametric., Comment: 50 pages, 14 figures. Final version

A uniform attachment graph (with parameter $k$), denoted $G_{n,k}$ in the paper, is a random graph on the vertex set $[n]$, where each vertex $v$ makes $k$ selections from $[v-1]$ uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well-studied random graphs: $k$-out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of $G_{n,k}$ to show that the conductance of $G_{n,k}$ is of order $(\log n)^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where, each vertex is either initially infected with probability $p$, independently of others, or gets infected later as a result of having $r$ infected neighbors at some point. We show that, for $2\le r\le k-1$, if $p\ll (\log n)^{-r/(r-1)}$, then, with probability approaching 1, the process ends before all vertices get infected. On the other hand, if $p\ge \omega(\log n)^{-r/(r-1)}$, where $\omega$ is a certain very slowly growing function, then all the vertices get infected with probability approaching 1.

Diaconis and Griffiths (2014) study the multivariate Krawtchouk polynomials orthogonal on the multinomial distribution. In this paper we derive the reproducing kernel orthogonal polynomials Q n ( x , y ; N , p ) on the multinomial distribution which are sums of products of orthonormal polynomials in x and y of fixed total degree n = 0 , 1 , … , N . The Poisson kernel ∑ n = 0 N ρ n Q n ( x , y ; N , p ) arises naturally from a probabilistic argument. An application to a multinomial goodness of fit test is developed, where the chi-squared test statistic is decomposed into orthogonal components which test the order of fit. A new duplication formula for the reproducing kernel polynomials in terms of the 1-dimensional Krawtchouk polynomials is derived. The duplication formula allows a Lancaster characterization of all reversible Markov chains with a multinomial stationary distribution whose eigenvectors are multivariate Krawtchouk polynomials and where eigenvalues are repeated within the same total degree. The χ 2 cutoff time, and total variation cutoff time is investigated in such chains. Emphasis throughout the paper is on a probabilistic understanding of the polynomials and their applications, particularly to Markov chains.

In this paper we make a comparison between certain probabilistic and deterministic point sets and show that some deterministic constructions (especially spherical t -designs) are better or as good as probabilistic ones like the jittered sampling model. We find asymptotic equalities for the discrete Riesz s -energy of sequences of well separated t -designs on the unit sphere S d ⊂ R d + 1 , d ≥ 2 . The case d = 2 was studied in Hesse (2009) and Hesse and Leopardi (2008). In Bondarenko et al., (2015) it was established that for d ≥ 2 , there exists a constant c d , such that for every N > c d t d there exists a well-separated spherical t -design on S d with N points. This paper gives results, based on recent developments that there exists a sequence of well separated spherical t -designs such that t and N are related by N ≍ t d .

In this paper we study the so called optimal polynomial meshes for domains in K ⊂ R d , d ≥ 2 . These meshes are discrete point sets Y n of cardinality c n d which have the property that ‖ p ‖ K ≤ A ‖ p ‖ Y n for every polynomial p of degree at most n with a constant A > 1 independent of n . It was conjectured earlier that optimal polynomial meshes exist in every convex domain. This statement was previously shown to hold for polytopes and C 2 like domains. In this paper we give a complete affirmative answer to the above conjecture when d = 2 .

This article concerns the asymptotic geometric character of the nodal set of the eigenfunctions of the Steklov eigenvalue problem $$\begin{aligned} -\Delta \phi _{\sigma _j}=0,\quad \hbox { on }\,\,\Omega ,\quad \partial _\nu \phi _{\sigma _j}=\sigma _j \phi _{\sigma _j}\quad \hbox { on }\,\,\partial \Omega \end{aligned}$$-Δϕσj=0,onΩ,∂νϕσj=σjϕσjon∂Ωin two-dimensional domains $$\Omega $$Ω. In particular, this paper presents a dense family $$\mathcal {A}$$A of simply-connected two-dimensional domains with analytic boundaries such that, for each $$\Omega \in \mathcal {A}$$Ω∈A, the nodal set of the eigenfunction $$\phi _{\sigma _j}$$ϕσj “is not dense at scale $$\sigma _j^{-1}$$σj-1”. This result addresses a question put forth under “Open Problem 10” in Girouard and Polterovich (J Spectr Theory 7(2):321–359, 2017). In fact, the results in the present paper establish that, for domains $$\Omega \in \mathcal {A}$$Ω∈A, the nodal sets of the eigenfunctions $$\phi _{\sigma _j}$$ϕσj associated with the eigenvalue $$\sigma _j$$σj have starkly different character than anticipated: they are not dense at any shrinking scale. More precisely, for each $$\Omega \in \mathcal {A}$$Ω∈A there is a value $$r_1>0$$r1>0 such that for each j there is $$x_j\in \Omega $$xj∈Ω such that $$\phi _{\sigma _j}$$ϕσj does not vanish on the ball of radius $$r_1$$r1 around $$x_j$$xj.

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

Given a graph $G$, a probability measure $\mu$ on the subsets of the edge set of $G$ is said to be $1$-independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$-ipm on $G$, and denote by $\mathbf{G}_{\mu}$ the associated random spanning subgraph of $G$. Let $\mathcal{M}_{1,\geqslant p}(G)$ (resp. $\mathcal{M}_{1,\leqslant p}(G)$) denote the collection of $1$-ipms $\mu$ on $G$ for which each edge is included in $\mathbf{G}_{\mu}$ with probability at least $p$ (resp. at most $p$). Let $\mathbb{Z}^2$ denote the square integer lattice. Balister and Bollob\'as raised the question of determining the critical value $p_{\star}=p_{1,c}(\mathbb{Z}^2)$ such that for all $p>p_{\star}$ and all $\mu \in \mathcal{M}_{1,\geqslant p}(\mathbb{Z}^2)$, $\left(\mathbf{\mathbb{Z}^2}\right)_{\mu}$ almost surely contains an infinite component. This can be thought of as asking for a $1$-independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$-ipms more generally. We give two lower bounds on $p_{\star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$-independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{1,G}(p)$ (respectively $F_{1,G}(p)$), the infimum (resp. supremum) over all $\mu\in \mathcal{M}_{1,\geqslant p}(G)$ (resp. all $\mu \in \mathcal{M}_{1,\leqslant p}(G)$) of the probability that $\mathbf{G}_{\mu}$ is connected. We determine $f_{1,G}(p)$ and $F_{1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$. Many new problems arise from our work, which are discussed in the final section of the paper., Comment: 43 pages, 3 figures

Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently at each iteration; and random-permutations cyclic (RPCD), which differs from CCD only in that a random permutation is applied to the variables at the start of each cycle. Known convergence guarantees are weaker for CCD and RPCD than for RCD, though in most practical cases, computational performance is similar among all these variants. There is a certain type of quadratic function for which CCD is significantly slower than for RCD; a recent paper by Sun & Ye (2016, Worst-case complexity of cyclic coordinate descent: $O(n^2)$ gap with randomized version. Technical Report. Stanford, CA: Department of Management Science and Engineering, Stanford University. arXiv:1604.07130) has explored the poor behavior of CCD on functions of this type. The RPCD approach performs well on these functions, even better than RCD in a certain regime. This paper explains the good behavior of RPCD with a tight analysis.

The purpose of this paper is to investigate the invariance of the arithmetic mean with respect to two weighted Bajraktarevic means, i.e., to solve the functional equation $$\begin{aligned} \left( \frac{f}{g}\right) ^{\!\!-1}\!\!\left( \frac{tf(x)+sf(y)}{tg(x)+sg(y)}\right) +\left( \frac{h}{k}\right) ^{\!\!-1}\!\!\left( \frac{sh(x)+th(y)}{sk(x)+tk(y)}\right) =x+y \qquad (x,y\in I), \end{aligned}$$ where $$f,g,h,k:I\rightarrow \mathbb {R}$$ are unknown continuous functions such that g, k are nowhere zero on I, the ratio functions f / g, h / k are strictly monotone on I, and $$t,s\in \mathbb {R}_+$$ are constants different from each other. By the main result of this paper, the solutions of the above invariance equation can be expressed either in terms of hyperbolic functions or in terms of trigonometric functions and an additional weight function. For the necessity part of this result, we will assume that $$f,g,h,k:I\rightarrow \mathbb {R}$$ are four times continuously differentiable.

The motivating question of this paper is roughly the following: given a group scheme $G$ over $\mathbb{Z}_p$, $p$ prime, with semisimple generic fiber $G_{\mathbb{Q}_p}$, how far are open subgroups of $G(\mathbb{Z}_p)$ from subgroups of the form $X(\mathbb{Z}_p)\mathbf{K}_p(p^n)$, where $X$ is a subgroup scheme of $G$ and $\mathbf{K}_p(p^n)$ is the principal congruence subgroup $\operatorname{Ker} (G(\mathbb{Z}_p)\rightarrow G(\mathbb{Z}/p^n\mathbb{Z}))$? More precisely, we will show that for $G_{\mathbb{Q}_p}$ simply connected there exist constants $J\ge1$ and $\varepsilon>0$, depending only on $G$, such that any open subgroup of $G (\mathbb{Z}_p)$ of level $p^n$ admits an open subgroup of index $\le J$ which is contained in $X(\mathbb{Z}_p)\mathbf{K}_p(p^{\lceil \varepsilon n\rceil})$ for some proper connected algebraic subgroup $X$ of $G$ defined over $\mathbb{Q}_p$. Moreover, if $G$ is defined over $\mathbb{Z}$, then $\varepsilon$ and $J$ can be taken independently of $p$. We also give a correspondence between natural classes of $\mathbb{Z}_p$-Lie subalgebras of $\mathfrak{g}_{\mathbb{Z}_p}$ and of closed subgroups of $G(\mathbb{Z}_p)$ that can be regarded as a variant over $\mathbb{Z}_p$ of Nori's results on the structure of finite subgroups of $\operatorname{GL}(N_0,\mathbb{F}_p)$ for large $p$. As an application we give a bound for the volume of the intersection of a conjugacy class in the group $G (\hat{\mathbb{Z}}) = \prod_p G (\mathbb{Z}_p)$, for $G$ defined over $\mathbb{Z}$, with an arbitrary open subgroup. In a future paper, this result will be applied to the limit multiplicity problem for arbitrary congruence subgroups of the arithmetic lattice $G (\mathbb{Z})$., fixed a few inaccuracies and made some stylistic changes to appear in JEMS