Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 110 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Use natural logarithms. A graph minor is represented by disjoint nonempty branch sets of a graph minor, each inducing a connected graph, with an edge between every pair. The complete graph minor density threshold is defined over nonempty finite graphs byIt uses , half the average degree of a vertex; the nonempty convention excludes the vacuous density inequality for the empty graph. The PDF has the intended definition with a universal implication over ; the TeX transcription corrupts that definition.
Probabilistic lower bound. Put and take the binomial random graph . Its edge count has mean . The Chernoff bound impliesWe show that the probability of a graph minor tends to zero. Ignore connectedness, which only enlarges the set of possible models, and assign each of the vertices one of branch labels or an unused label. There are at most assignments.
For any assignment with nonempty branch sets, at least of them have size at most . Between any two such small sets , the probability of no edge isThe absence or presence of edges between different pairs of branch sets depends on disjoint sets of random edges, so these events are independent. For this assignment the probability that all small pairs are adjacent is at mostThe union bound over assignments is therefore at mostsince the positive term is and the negative term has order . There is consequently a graph with no graph minor and with . Any constant having the universal forcing property must exceed this ratio. Since for large ,
The auxiliary density lemma contains a typo. Both the original PDF and the TeX print in the hint. This cannot imply its conclusion: for , an edgeless graph has only edgeless graph minors, and none satisfies . We use the intended dense minor with bounded order and high minimum degree lemma with the hypothesis for nonempty . The upper-bound argument below depends on that corrected supplied lemma; the literal printed hint is false.
Probabilistic upper bound and the constant seven. Suppose is nonempty and , and setThe corrected lemma gives a graph minor of order with . Since , we also have . For large , every vertex has at most nonneighbours, counting itself, becausethe last inequality uses . Moreover any two distinct vertices have at leastcommon neighbours.
Choose disjoint random -sets from , uniformly, which is possible since for sufficiently large . For a set , let be the set of vertices having no neighbour in . For each vertex, the probability that all members of a uniformly sampled -set are its nonneighbours is at most , even when sampling without replacement. By linearity of expected value,Call good if . The Markov inequality shows that a random set is bad with probability at most . Thus the expected number of bad sets among our samples is .
Conditional on a fixed good , the marginal distribution of is uniform among -sets outside . For there to be no edge between them, all its members must lie in . HenceHere . Consequently the expected number of nonadjacent pairs of good sets is at mostsince . Applying the Markov inequality to both counts shows that there exists a choice with fewer than bad sets and at most nonadjacent pairs of good sets. Select of the good sets; they still have at most missing adjacencies.
Make each selected set connected by fixing one of its vertices as a root and, for each of its other members, adding one unused common neighbour of that member and the root. This uses at most additional vertices. Then for each pair with no original edge, choose one vertex in each set and add an unused common neighbour to one of the sets. The added vertex is joined to that set and to the other set, so it preserves connectedness and repairs their adjacency. At most such repairs are required.
Throughout this process the total number of occupied vertices is at mostSince every pair has at least common neighbours, an unused choice always exists. The final sets are disjoint connected branch sets of a graph minor with every pair adjacent. They represent in , and hence in , by transitivity of graph minors. This random branch-set construction of a complete graph minor proves
The sharp linear threshold for a four-vertex complete minor. We prove by induction that a graph on vertices with at least edges has a graph minor. The case is itself. If some edge has at most one common neighbour, an edge contraction reduces the order by one and removes exactly edges. The contracted graph has at least edges, so induction applies.
Otherwise every edge is in at least two triangles in a graph. Choose a vertex incident with an edge. Each vertex has at least two neighbours of a vertex in , since these are the common neighbours of . Thus has minimum degree of a graph at least two. A longest path in this finite graph has an endpoint adjacent to an earlier nonconsecutive path vertex, and hence contains a cycle in a graph. Together with , this cycle in a graph gives a wheel graph as a subgraph. Divide its rim into three consecutive nonempty connected arcs; these arcs and form four pairwise adjacent branch sets of a graph minor. Therefore
With edges the answer is no. Take the join of graphs of and an independent set of vertices. It has edges. Among four disjoint putative branch sets of a graph minor, at most two can contain the two vertices of . Any connected branch set avoiding them is a singleton in the independent set. At least two such singleton sets would therefore have no edge between them. This excludes a graph minor for every and proves sharpness.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 110 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Statement and definitions. For disjoint nonempty sets of vertices, their edge density of a bipartite graph is . They form a regular pair of vertex sets, or an -uniform pair, ifwhenever , , and .
The Szemerédi regularity lemma states that for every and positive integer , there are integers such that every graph of order has a set partitionwith , , equal nonzero sizes , and at most unordered pairs , , that fail to be -uniform. It is enough to prove this for , since decreasing the parameter strengthens the conclusion.
Energy increment. For the proof, regard each exceptional vertex as a singleton part and use the equitable regularity energyThe sum is over ordered pairs, including diagonal pairs; for those pairs define as the mean adjacency indicator on . Thus . Under a refinement, the subrectangle densities have the original density as their weighted mean. The Cauchy-Schwarz inequality, equivalently the nonnegativity of their weighted variance, gives .
Suppose there are more than irregular pairs, with main cell size . For each such pair choose witnesses , of sizes at least and with . Refine every main cell by all its witness subsets. Each splits into at most atoms, and we may use the larger bound .
For an ordered irregular rectangle, write its refined densities as and relative areas as . The energy gain on that rectangle isThe witness rectangle has relative area at least . Applying the Cauchy-Schwarz inequality to the subrectangles it contains shows that this expression is greater than . There are two orientations of each irregular pair. Since , the total gain is greater than
Restoring equal sizes without losing energy. Put , assuming . Split every refined atom into sets of size , putting its leftover fewer than vertices into the exceptional set as singleton parts. This is a further refinement, so the energy cannot decrease. The number of new exceptional vertices is at mostThe number of new main cells satisfiesFor the first inequality, in each old cell the leftovers have total size less than , so at least one full chunk survives. All previous exceptional singleton parts are kept. Treating leftovers as singleton parts is what makes the energy increment survive equitabilization exactly.
Take and choose so large that . Start with equal main cells, with fewer than exceptional vertices. Define a finite bound by iterating a total of times, starting from . Choose sufficiently large that and whenever .
At each of the first refinements, the exceptional set has size at mostthe cell count is between and , and , so all the chunk sizes above are valid. But unsuccessful refinements would raise by more than , which is impossible. Thus the procedure terminates at a partition satisfying the Szemerédi regularity lemma.
Three linearly large uniform sets. Apply the Szemerédi regularity lemma withFor , delete all edges touching , all internal main-cell edges, all edges of irregular pairs, and all edges of regular pairs whose edge density of a bipartite graph is less than . The respective losses are bounded byThus the total loss is at most , and the remaining graph has at leastedges. Form the reduced graph of a regularity partition , joining two main cells precisely when they are -uniform and have edge density of a bipartite graph at least . If their common size is , the remaining edge count is at most . Since , we obtain . The Mantel theorem gives a triangle in a graph in . Its three cells have the required pairwise density and are -uniform: an -uniform pair is uniform for any larger parameter.
Each selected cell has size . ChooseFor , the Mantel theorem gives a triangle in a graph in the original graph, since its edge count exceeds ; take its three singleton vertices. Their pairs have density one and are uniform for every positive parameter, and . Therefore in all casesThe constant is absolute; the energy proof gives a very large bound for , which does not affect its positivity.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 110 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Symmetrization for an arbitrary real coefficient. Among graphs maximizing , choose one maximizingFor a vertex , put . This is the contribution of edges and triangles in a graph containing . If are nonadjacent, Zykov symmetrization replacing by a clone of changes by ; the opposite replacement changes it by . Maximality implies , so both changes preserve .
Let and . In the first replacement the vertex degrees in increase by one and those in decrease by one; in the opposite replacement these changes reverse. The changes to cancel when the two replacements are added. Since ,If the two vertex neighbourhoods differ, one replacement increases , a contradiction. Thus every pair of nonadjacent vertices has the same vertex neighbourhood. Nonadjacency, with equality allowed, is an equivalence relation: if and are nonadjacent and and are nonadjacent, their identical vertex neighbourhoods forbid as well. Its classes are independent sets and every cross-class edge is present. ThereforeThis edge-triangle symmetrization works for either sign of .
The exact supporting line. For , writeWe prove the triangle support line between bipartite and tripartite Turan graphs by maximizing . First . For , its values are respectively . For , the exact balancing of the Turán graph gives , while and the arithmetic-geometric mean inequality gives . Hence
By edge-triangle symmetrization a maximizing graph can be taken complete multipartite graph; among such maximizers use one with the fewest nonempty parts. If there are at least four parts, let be the two smallest sizes. Then . Merging them loses edges and triangles in a graph, so the objective changes byThis contradicts the choice of the number of parts. Thus at most three parts remain.
For three part sizes , the objective isIf , merging the parts of sizes does not decrease it, again contradicting minimality. If and , transferring one vertex from the largest to the smallest part raises by and strictly increases the objective. Thus a three-part maximizer has all sizes differing by at most one, and is . A maximizer with at most two parts has objective at most , since it has no triangles in a graph and the Mantel theorem bounds its edges. Finally,Therefore every graph satisfies . At the prescribed edge count this givesFor , the conclusion is simply the nonnegative lower bound zero. All rounding in the Turán graphs has been retained.
One edge above the bipartite threshold. Write . We prove the Triangle lower bound one edge above the Mantel threshold by induction on , allowing at least edges. For , five edges on four vertices give two triangles in a graph, and adding edges preserves this bound.
We will also use the following consequence of an inductive bound: on vertices, at least edges, for an integer , force at least triangles in a graph. Delete surplus edges first to leave exactly . Repeatedly delete an edge in a triangle in a graph until edges remain. The Mantel theorem guarantees such a triangle in a graph at every step; each deletion destroys at least one distinct triangle in a graph. Apply the inductive bound to the remaining graph.
Now take exactly edges. If every edge lies in a triangle in a graph, the edge-triangle incidence bound gives . This is at least for ; the base case was handled separately.
Otherwise choose an edge in no triangle in a graph. Its endpoints have disjoint vertex neighbourhoods, so . Deleting removes exactly edges and leaves at least edges. If , it leaves at least edges, and the strengthened inductive bound gives at least triangles in a graph already.
If , induction gives at least triangles in a graph after deletion. There must be an additional triangle in a graph containing or . Otherwise both and are independent sets; since they are disjoint and cover all vertices, would be bipartite graph, contradicting by the Mantel theorem. HenceThe bound is sharp: add one internal edge to one class of the complete bipartite graph . Its triangles in a graph are precisely that edge together with each of the vertices in the other class.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 110 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write . The Erdős-Stone theorem states that, for a fixed graph with chromatic number ,Here is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write for the balanced complete multipartite blow-up with classes of vertices each. All asymptotic errors below concern with the forbidden graphs fixed.
The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For , the edgeless spanning subgraph suffices. Suppose .
First repeatedly remove a vertex whose degree of a vertex is less than times the current order, where sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every -free subgraph of order at most ,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to . If vertices survive, the removed edges number at mostComparing with shows that , provided dominates , the initial relative error, and . Consequently . The surviving induced subgraph satisfies and .
By the Erdős-Stone theorem, contains for some as slowly as necessary. This follows because exceeds the extremal number density for each fixed by the positive gap . Choose so slowly that and , and denote its root classes by .
An outside vertex having at least neighbours of a vertex in every determines one choice of a -subset in each . At most outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form . Thus at most outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class for which it has fewer than neighbours of a vertex in .
Write , with . Counting missing incidences with givesSince , it follows that for every . The total missing incidences from all root vertices to assigned vertices are at most . At least of them are incidences with a vertex's own assigned root class. Hence only missing incidences go to other root classes.
Choose slowly and discard the assigned vertices with more than missing incidences to other root classes. Each remaining vertex of is adjacent to all but at most vertices of every , . If its class contained a complete bipartite graph , the vertices of this copy would have at least common neighbours of a vertex in each other root class. These sets extend the copy to , a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is .
The surviving graph still has edges, whereas the total possible cross-class edges, with these balanced classes, is . Thus only cross-class edges are missing. Discard the vertices missing more than cross-class edges, with slowly, and delete all internal edges. The resulting -partite subgraph has classes of size andFor the lower bound, every surviving vertex misses only vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.
Minimum degree in an extremal graph. Fix with . Choose large enough that embeds in . An extremal -free graph is therefore -free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For take as above.
For any vertex , remove and introduce a new vertex whose vertex neighbourhood consists precisely of the vertices in other than . The new degree of a vertex is . This new graph remains -free. Indeed, a new copy of must use , and all its neighbours of a vertex in that copy lie in the other classes of . There are only boundedly many of them. Each misses only vertices in , so an unused vertex is adjacent to all of them. Replacing by would give in , which is impossible.
Extremality now forces , uniformly in . The upper bound for the minimum degree of a graph follows from . For , already gives . ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.
The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turán graph contains no , so every such clique in uses a vertex of . Therefore contains no vertex-disjoint such cliques, and the extremal number is at least .
Induct on , with supplied by the Turan theorem, including its equality characterization. Let and let be extremal for . The preceding results give and the -partite subgraph . Keep its classes fixed and assign each of the remaining vertices to a class in which it has fewest neighbours of a vertex in . Write the resulting classes as ; all have size . Choose a positive so slowly that dominates the outside count, every cross-class error in , and every error in the minimum degree of a graph bound.
Suppose some vertex has at least internal neighbours of a vertex. If , the assignment rule shows that has at least neighbours of a vertex in every . If , it has this many in and in the other . If contained disjoint , we could choose one vertex in each , successively avoiding those copies and the missing cross-neighbours of the already chosen vertices. This produces a further through . For , this just chooses an unused neighbour of . Hence is -free, and induction givesSince the candidate attains , equality holds throughout: is a universal vertex and is the inductively unique extremal graph. Thus is isomorphic to .
It remains to show that this case must occur. Otherwise all internal vertex degrees are less than . Together with the lower bound on and , this implies that every vertex misses only vertices outside its own class. If some contains a matching in a graph of edges, extend its edges one by one to , choosing one vertex from each other class. At every step only cross-neighbours and boundedly many used vertices are excluded. This gives disjoint forbidden cliques, a contradiction.
A maximal matching in each class therefore has at most edges, and its at most endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all , so the total internal edge count is . The cross-class edge count is at most , whenceBut the balanced part sizes of the Turán graph givecontradicting extremality for . This argument also works for . Consequently, for all sufficiently large ,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 108 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
The Rudolph measure rigidity theorem has an essential ergodicity hypothesis. If a Borel probability measure on the circle group is invariant under both and , is ergodic for the semigroup generated jointly by these maps, and either map has positive Kolmogorov-Sinai entropy, thenEquivalently, a jointly ergodic common invariant measure other than Lebesgue measure has zero entropy for both maps. Joint ergodicity means that every set invariant modulo under both maps has measure zero or one. Positive entropy without this hypothesis is insufficient: , with a Dirac measure, is a common invariant measure of positive entropy and is not .
The Host equidistribution theorem states that if are relatively prime integers and is invariant and ergodic under , with , then for -almost every the sequence is an equidistributed sequence for Lebesgue measure. Explicitly, for every continuous on the circle,The non-ergodic form assumes invariance and positive entropy for almost every component in the ergodic decomposition . Applying the ergodic theorem of Host on each such component gives the same almost-everywhere conclusion for . More generally, its conclusion holds on the part supported on positive-entropy components. A positive value of alone does not eliminate zero-entropy components.
To deduce the joint version of the Rudolph measure rigidity theorem, suppose ; if only has positive entropy, interchange the roles. Write the ergodic decomposition as . Since commutes with , its pushforward measure sends a ergodic component to a ergodic component . On each component, is a factor of a measure-preserving system with fibres of size at most three. We use the standard entropy preservation under a finite-to-one factor:The reason for this standard entropy fact is that, conditional on a complete factor point, every finite orbit name has at most three possibilities; its conditional entropy is bounded by , and division by the orbit length gives zero relative entropy.
The component at is almost everywhere; this follows from commutation and the componentwise ergodic averages. The component entropy function is therefore invariant under both and . Joint ergodicity makes it constant almost everywhere, and affinity of entropy under ergodic decomposition identifies the constant as . Thus almost every component has positive entropy, exactly the condition required in the non-ergodic Host equidistribution theorem. It follows that -almost every point equidistributes for under .
For any continuous , invariance under and the dominated convergence theorem now giveContinuous functions determine Borel probability measures on the circle, so , proving the deduction.
For the normal-number example, let be independent fair binary digits and defineThis Cantor Bernoulli measure is supported on the middle-third Cantor set . If is the Bernoulli shift, then on the circle. Consequently is invariant and ergodic: a invariant event pulls back to an invariant event, which has probability zero or one.
Take the ternary digit measurable partition . Its block partition of length has, up to null endpoints, positive-measure atoms under , each of measure , and all other atoms have measure zero. HenceApply the Host equidistribution theorem with , . For -almost every , the sequence equidistributes for Lebesgue measure, so is a normal number in base by normality and equidistribution under integer multiplication.
The ternary expansion of -almost every such contains only and , so the frequency of digit is zero rather than . The ambiguous ternary endpoints form a countable null set and can be removed. Therefore is not a normal number in base . We have proved the stronger almost-everywhere existence statement
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 108 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let denote the join of measurable partitions recording the first observations, and set , with . The entropy of a countable measurable partition is , using natural logarithms and . Null atoms can be discarded. Throughout, is a probability measure.
The stronger property needed for monotonicity of normalized block entropy is that its increments decrease. DefineSince conditioning reduces entropy, . The conditional entropy chain rule and measure preservation giveIt follows that , and consequentlyThis uses stationarity as well as the entropy chain rule; subadditivity alone would not establish monotonicity of every successive ratio.
The entropy rate of a measurable partition and the Kolmogorov-Sinai entropy are, respectively,One may equivalently take the supremum over countable finite-entropy measurable partitions.
The Shannon-McMillan-Breiman theorem states that for a countable measurable partition with , the normalized informationconverges almost everywhere and in to a invariant function with integral . Here is the atom containing . If is an ergodic transformation, then almost everywhere. We prove the general form, including an explicit formula for its limit.
Let be the sigma-algebra generated by , let be trivial, and put . For every atom , the probabilitiesform a bounded conditional-expectation martingale. The martingale convergence theorem gives almost everywhere and in . Each of these probabilities is positive almost everywhere on : for example, integrating over the measurable set gives zero. Countability of lets us choose a common full-measure set for every atom.
The conditional information functionstherefore converge almost everywhere to . We need an integrable bound on this sequence; convergence of the probabilities alone would not supply one after taking logarithms. The allowed maximal inequality for conditional information functions gives, for ,Combining this with the bound by and the tail integral formula for moments yieldsThus , and the dominated convergence theorem gives in . In particular,because is the average of the decreasing sequence .
The information chain rule, applied from the final observation backwards, gives the exact identityIndeed, the symbol at time is conditioned on times ; pulling that conditional probability back by gives . Measure preservation is sufficient for this pullback identity.
We now prove the required triangular ergodic averaging lemma in this instance. Put . Then almost everywhere, , and . Split the difference between the displayed triangular sum and . Terms whose index is at least are bounded by . The remaining terms are at mostAfter division by , each of these finitely many end terms tends to zero almost everywhere by the linear growth bound for integrable observables proved in Question 1. Applying the Birkhoff ergodic theorem to , for every fixed , therefore givesThese conditional expectations decrease to zero almost everywhere: they decrease, and their integrals tend to zero. Letting , then applying the Birkhoff ergodic theorem to , proves
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 108 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
For an increasing sequence of nonnegative integers, full-density sequence means that its range has natural density one:For a sequence in a metric space, convergence in density of a sequence to means that, for every ,In particular, a bounded nonnegative scalar sequence converging to zero in density has averages tending to zero: the average is at most plus its bound times the proportion of indices above .
Here is a Hilbert space form of the Van der Corput lemma, including the density version. Suppose , and putThenSince , it suffices for to converge to zero in density. A frequently used special case is that the correlation average tends to zero for every fixed .
To prove the lemma, extend the finite list by zero outside this range, and write . For ,The Cauchy-Schwarz inequality for this sum, followed by expansion of the squared Hilbert space norm, givesThe coefficient counts the pairs of shifts separated by . Dividing by , bounding real parts by absolute values, and first taking the limit superior in for fixed yieldsThe right side tends to zero as under the stated hypothesis. This proves both the lemma and its density consequence.
For the polynomial application, fix a nonzero integer and let . For each fixed , the correlation phase is linear:Thus, with ,The coefficient is irrational, so . This geometric series is bounded in modulus by and tends to zero. All vanish, so the Van der Corput lemma gives
The Weyl criterion now shows that the fractional parts form an equidistributed sequence. For completeness, its sufficiency here follows directly: the displayed limits give the correct average for every trigonometric polynomial, including the constant term. The Stone-Weierstrass theorem extends this to every continuous function by uniform approximation. Approximating an interval's indicator function above and below by continuous functions gives its length as the limiting frequency. HenceThis proves the equidistribution of a quadratic polynomial with irrational leading coefficient using the required correlation argument.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 108 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Use the probability-system convention . The Birkhoff ergodic theorem, also called the pointwise ergodic theorem, states that for a measure-preserving system and ,where is the invariant sigma-algebra. The limit is integrable and has the same integral as . On a probability space the convergence also holds in , as in the allowed mean ergodic theorem. If is an ergodic transformation, is trivial modulo null sets, giving
The integer multiplication map on the circle preserves Lebesgue measure: for any integrable on ,To prove the ergodicity of integer multiplication on the circle, suppose satisfies . Let be its Fourier coefficients in the Fourier basis . Since , the Fourier coefficients of at index are zero if does not divide , and are otherwise. This identity holds for all functions by approximation with trigonometric polynomials and the isometry . Invariance givesEvery nonzero integer can be divided by only finitely often. Thus for every , and completeness of the Fourier basis makes constant almost everywhere. Applying this to the indicator function of an invariant set gives measure zero or one, so
A normal number in base has every word of base- digits occurring with limiting overlapping frequency . Use the expansion that is not eventually equal to when there are two expansions. The word corresponds to the half-open intervalA word starting at position occurs exactly when . The Birkhoff ergodic theorem, applied to , gives frequency almost everywhere. There are countably many pairs , so their full-measure sets have a full-measure intersection. In particular,These are absolutely normal numbers, so existence follows as well. This interval description also proves normality and equidistribution under integer multiplication: the base- intervals form arbitrarily fine grids, so their frequencies imply the correct frequency for every interval by approximation from inside and outside.
For the growth assertion, put . For every , the Tonelli theorem gives the useful summability boundSince is a measure-preserving transformation, . The first Borel-Cantelli lemma shows that occurs only finitely often almost everywhere. Intersecting the resulting full-measure sets for proves the linear growth bound for integrable observables, . Multiplication by then gives
The threshold is sharp. For , choose with , and take the Bernoulli shift on with the product measure of independent uniform coordinates. The left shift preserves that measure because it preserves the probability of every finite-coordinate event. Define ; it is integrable becauseThe variables are independent. For any fixed ,The probability sum diverges, so the second Borel-Cantelli lemma makes these events occur infinitely often almost surely. Intersecting over positive integer even yields . For , the constant observable already fails to give limit zero. Thus the sharpness of the linear growth bound for integrable observables gives
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





