text:
Radiolab has a show on randomness (the embed feature doesn’t work) where they discuss an experiment of flipping a coin 100 times. A string of tails appeared 7 times, which seems to be relatively small. Indeed, given 7 coin tosses, the probability of all 7 coming up tails is
$$\frac{1}{2^7} = \frac{1}{128} \approx 0.007812 \text{.}$$
As an aside, the probability of all coming up the same side is $\frac{1}{2^6}$ because the initial toss does not matter. All that matters is that all subsequent tosses match.

The discussion sets up an experiment where one group flips a coin 100 times and a second group says they flip a coin 100 times and each reports the results. A statistics professor can then tell the difference because the group that actually flipped the coin got a string of 7 tails which seems unlikely, but is more likely than you think. The show notes that the probability of getting 7 tails is 1 in 6 because there are 14 groups of 7 in 100. Which in one sense is true. But with overlap, there are 94 groups of 7 any one of which can be all tails. So the probability of getting a string of exactly 7 tails is really
$$1 – \big(\frac{127}{128}\big)^{94} \approx 0.521576 \text{.}$$
Or just more than half of all sets of 100 flips will contain a string of 7 tails. And if we can allow that we don’t care about whether the string of 7 is either heads or tails, the probability jumps to more than three-quarters:
$$1 – \big(\frac{63}{64}\big)^{94} \approx 0.772440 \text{.}$$
These are all a lot more than the 1 in 6 Radiolab claims.

1. All due respect, Ton’ (to quote from the The Sopranos), but unless I’m missing something this calculation doesn’t sound correct. As I understand your reasoning, if we were dealing with 10 coin flips rather than 100 then your estimate would be 1 – (127/128)^4 = ~0.030886 for the probability of getting 7 tails in a row.

Per my own calculation there are 12 ways to get exactly 7 tails in a row in flipping 10 coins: TTTTTTTHHH, TTTTTTTHHT, TTTTTTTHTH, TTTTTTTHTT, HTTTTTTTHH, HTTTTTTTHT, HHTTTTTTTH, THTTTTTTTH, HHHTTTTTTT, THHTTTTTTT, HTHTTTTTTT, TTHTTTTTTT. Since there are 2^10 = 1024 possible outcomes, this corresponds to a probability of 10/1024 = ~0.011719, much lower than the value by your method.

If we’re talking about the probability of getting 7 *or more* tails in a row in 10 coin flips then there are 20 ways to do this (see below), for a probability of 20/1024 = ~0.019531, again lower.

R code for calculation in previous paragraph:

x <- rep("", 1024)
for (i in 1:1024) {
x[i] <- paste(as.numeric(intToBits(i)[1:10]), collapse = "")
}
sum(grepl("1111111", x))

One good discussion of how to compute the probability of a run of K or more tails in N coin flips is at http://www.askamathematician.com/2010/07/q-whats-the-chance-of-getting-a-run-of-k-successes-in-n-bernoulli-trials-why-use-approximations-when-the-exact-answer-is-known/

Using the Python code from that page the probability of getting a run of 7 or more tails in 100 coin flips is 0.317520. The probability of getting a run of exactly 7 tails is of course less than that number.

1. Well, a few things. First, your count is off. Let’s assume this os limited 7 tails, just to simplify the discussion. There are, essentially, 4 ways to get 7 tails in a row. TTTTTTTXXX, XTTTTTTTXX, XXTTTTTTTX, and XXXTTTTTTT, where X can be either T or F. There are $2^3 = 8$ possibilities for X, so that’s $8 * 4 = 32$ total out of the 1024 options.

2. Your count is off. Let’s assume this is limited 7 tails, just to simplify the discussion. There are, essentially, 4 ways to get 7 tails in a row. TTTTTTTXXX, XTTTTTTTXX, XXTTTTTTTX, and XXXTTTTTTT, where X can be either T or F. There are $2^3 = 8$ possibilities for X, so that’s $8 * 4 = 32$ total out of the 1024 options.

So that is $32/1024 = 0.03125$. That’s pretty close to my estimate of $1 – (127/128)^4 approx 0.03088569268$, but I am reasonably convinced my original method is correct, still. I am open to suggestion about why it might not be.

1. Aren’t you double-counting a bit? For example, if you take TTTTTTTXXX and choose XXX = TFF you get TTTTTTTTFF. But if you take XTTTTTTTXX and choose XXX = TFF you also get TTTTTTTTFF. More obviously, if you choose XXX = TTT then all four base sequences produce the sequence TTTTTTTTTT. So the eight possibilities for XXX will not produce 32 distinct sequences from the four base sequences.

That’s why I did the thing with the R code: Every integer from 0 to 1023 corresponds to a unique bit string of length 10. So finding all the bit strings in that list with 7 or more 1’s will produce the correct count.


text:
# Solutions to Problems 285-296 (Vol. 11 No. 3)

Q.285 C.F.Gauss was given the problem of summing the numbers from 1 to 100 when he was a student. He did it this way:

format: plain


text:
[Maxima] Is it possible to test packages to solve domain, equations and inequalities, interval arithmetic functions.

Mihail Denisenko mihail22 at nigma.ru
Fri Nov 27 08:14:56 CST 2009

Hi.
Thank you for attention to my letter.
*If it would be possible for You, please, try to test these packages.*

This simple project is related to modification of Maxima's solver (equations
and inequalities).
Using domain function in the solver to eliminate wrong roots from the final
result of the function.

I have developed new functions:
1) module that computes domain of superposition of elementary functions;
2) interval arithmetics module;
3) module to solve equations and inequalities.

Modules to solve inequalities ond compute domain are located in the same
file "ineq_domain.mac".
Module to solve equations is located in the "solve_equation.mac".
Interval arithmetics functions are written in the
"interval_arithmetics.mac".

1), (inequality 3)) Package to solve inequalities is based on idea of
"solve_rat_ineq" and
package "fourier_elim". It can solve polynomial and rational inequalities,
and linear
inequalities with functions abs(), max(), min() and simple cases that can be
reduced to linear ones.
This package produces answer - internal representation of lists of
intervals. It uses
package "interval_arithmetic" to perform basic operations with intervals and
lists of intervals:
intersect, combine, exclude, etc. (comments on internal arithmetic functions
are written in source
file "interval_arithmetic.mac".)
Internal representation from the function 'solve_ineq' is used to compute
domain of mathematical
expressions. It process superposition of functions and accumulate list of
all sub-domains for
subexpressions. Basic points to compute domain are functions:
f(x)/g(x), log(f(x)), (f(x)^(g(x)), tan(x), cot(x), sec(x), csc(x), asin(x),
acos(x),f(x)^(negative exponent).

Functions: domain_return(expr, var), solve_ineq(ineq, var) --- produces
result in
the internal representation of lists of intervals, single points, periodic
results and
unsolved expressions.

Functions: solve_inequality(ineq, var), domain_solve(expr, var) --- produces
result in
the TeX-form. It can be used to output results as images or .pdf and .ps
text.

2) Internal arithmetics package is used in solving domain, equality and
inequality.
Description of basic functions is located in the file
"interval_arithmetic.mac".
If the function does not include in its name suffix _strict_, it handles
input parameters
as the set of segments (The boundary points of intervals are included). If
a function
name contains the suffix _strcit_, then the input and output values of
intervals, and
segments should be interpreted as follows:
______________________________
_________________________________
Internal representation    ||||    Mathematical representation

--------------------------------------------------------------------------------------------------
|     [a,b]                           ->
(a,b)              |
|     [[a,a],[a,b]]                ->
[a,b)              |
|     [[a,b],[b,b]]                ->
(a,b]              |
|     [[a,a],[a,b],[b,b]]        ->
[a,b]              |

----------------------------------------------------------------------------------------------------

3) Package to solve equations. It uses functions 'solve' and
'to_poly_solve'. Some steps of the
solution are displayed. Before solution of the equation it does
preprocessing to check domain of
expression, check some classes of equations and special processing.
Result contains roots from real domain only (Russian school's program does
not contain imaginary domain
and this packages will be used for special school program).
This module catches errors of 'to_poly_solve' (if it can not solve) and
produces corresponding result
without error message.

This module is written to solve single equations with one variable (mainly).
But it has some processing
of systems of equations (in that case it calls 'solve' function to solve the
system of equations).

After solving of equation this module does post-processing to discard roots
that are not in the domain of
initial equation.
Result is the list of explicit roots (or intervals:  x/x=1 => (minf, 0), (0,
inf)), periodic roots, unsolved
expressions.

In some cases solver have to turn off Maxima's simplifier: it is necessary
to compute domain for some
expressions before simplification stage. For example: asin(x)/asin(x)=1. If
simplifier is turned on then result
is [minf, inf]. Else if simplifier is turned off then result is [-1, 0), (0,
1]. For equation
((x+1)/(x+1)+(2*x+3)/(2*x+3))/((x^2-4)/(x^2-4))=2 result is (minf, -2),(-2,
-3/2),(-3/2, -1), (-1, 2), (2, inf)

(or in TeX-form $$x\in\left( -\infty ,-2\right)\cup\left(-2,-{{3}\over{2}}\right)\cup\left(-{{3}\over{2}},-1\right) \cup\left(-1,2\right)\cup\left(2,\infty \right)$$)

Interesting example of using simp:false.

If simp:true then function solve(1.3^x=6, x) and function
to_poly_solve(1.3^x=6, x) can not solve it.
If simp:false then solve produces correct result - correct root
log(6)/log(13/10)
$$x={{\log 6}\over{\log \left({{13}\over{10}}\right)}}$$

Function: solve_equation(equation, vars) --- produces result in TeX-form
expression.
-----------------------------------------------------------------------------------------------------------
!!!!!!Warning!!!!!!!!!!
Before using of these modules You should do:

All functions of the above-mentioned packages should process some cases when
simplifier is turned off.
Instruction for usage of functions:
1. before each function call you should do simp:false;
2. then function call: solve_equation(expr, var),
solve_inequality(expr, var),
domain_solve(expr, var),
solve_ineq(expr, var),
domain_return(expr, var);
3. after function call you should do simp:true. It is necessary due to
correct working of other Maxima's functions.

Example:
simp:false,
solve_equation((x+1)/(x+1)+(2*x+3)/(2*x+3)=2,x),
simp:true,

simp:false,

solve_equation(1/x*sin(sqrt(cot(1/(x-sin(log(asin(x)))))))+acos(tan(x+10))+(1+x)^(x*sqrt(x+2*cos(x)))=0,x),
simp:true,

simp:false,
solve_inequality((x-1)/(x-2)*(x-3)/(x-4)*(x-5)/(x-6)>=0,x),
simp:true,

simp:false,

domain_solve(sqrt(abs(x)-7*x)+asin(1/1000000*x)/(x^2-16)+log(abs(x+5)-4)+(x-1)/(x-1)+(100000000-x^4)^(25*x)=0,x),
simp:true,

-------------------------------------------------------------

I work at solve_inequality package to add processing of new cases:
/* TODO: Inequality preprocessor
* Analyze type of the equation:
*  - with abs function,
*  - with square roots,
*  - with exponentiation,
*  - with logarithms,
*  - with trigonometric and arc-trigonometric functions
*/
Also I am going to add special processing of periodic solutions --- correct
intersection, combination, output.

--------------------------------------------------------------
If it would be possible for You, please, try to test these packages.

Best regards,
Mihail Denisenko
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.math.utexas.edu/pipermail/maxima/attachments/20091127/fd44680b/attachment-0001.htm
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solve_domain.zip
Type: application/zip
Size: 13965 bytes
Desc: not available
Url : http://www.math.utexas.edu/pipermail/maxima/attachments/20091127/fd44680b/attachment-0001.zip


text:
# [SciPy-user] scipy on XP isnt happening -- and: concerning confusions

Gary Pajer gpajer at rider.edu
Tue Dec 13 08:50:24 CST 2005

Sven Schreiber wrote:

>Gary Pajer schrieb:
>
>
>>Martin Somers wrote:
>>
>>
>>
>>
>>>[...]
>>>
>>>when i try installing scipy_core
>>>python setup.build
>>>python setup.install .....
>>>
>>>
>>>
>
>Maybe I don't understand your (ie., Martin's) problem, but the installation on windwos with the
>binary installers is actually quite simple, no need to do builds, compilations and distutils stuff
>
>
Correct, of course.   In looking back at Martin's post, I see that he
listed some binary installers.  Maybe he is indeed looking for a simple
installation procedure.  If  so, see Steve's instructions below.  (what
is pywin32??  I don't think I have it;  if that's true, it would be
unnecessary)

I always have trouble finding the binaries.  scipy_core is at:

http://sourceforge.net/project/showfiles.php?group_id=1369&package_id=6222

But IIRC,  scipy is somewhere else... and I can't find it at the moment.

latest tweaks.

[aside:  a few things have confused me over that past few weeks.  One is
the above-mentioned difficulty in finding the binary installers.
Another is the similarity of the names "scipy" and "scipy core"  and the
occasional use of "scipy" to mean the combination of the two, and my own
use of the word "scipy" when I really mean "scipy core".   I don't
suppose it's advisable to change the names now, but as the dust
settles,  a clear paragraph or two on the scipy home page, with clear
pointers to the appropriate files.   Personally, I'd vote to see the
names changed ... Maybe take the "sci" out of scipy core, since it has
application beyond scipy.  NuCore?  I don't know.]

>>From your earlier message it seems maybe you're missing the win32-extensions of python? (Before
>installing scipy and stuff.)
>
>I used, in that order (as admin, but have also installed on a different machine w/o admin rights,
>but of course only in "my documents"):
>python-2.4.2.msi
>pywin32-205.win32-py2.4.exe (these are the infamous extensions mentioned above)
>scipy_core-0.6.1.win32-py2.4.exe
>scipy-0.4.3.win32-py2.4.exe
>(can add wxPython here as well if you like)
>
>and then for matplotlib:
>Numeric-24.2.win32-py2.4.exe (should/will be unnecessary in the future)
>matplotlib-0.85.win32-py2.4.exe
>
>
>
>
>>Try this:
>>http://www.scipy.org/mailinglists/mailman?fn=scipy-user/2005-November/005872.html
>>
>>I had to use MinGW 3.1 to get it to work.  MinGW 4.1 didn't work.
>>Get the atlas binary,
>>set ATLAS=c:\path\to\atlas
>>
>>
>>
>
>I don't think that's what he (Martin again) wants, see above.
>hth, sven
>
>_______________________________________________
>SciPy-user mailing list
>SciPy-user at scipy.net
>http://www.scipy.net/mailman/listinfo/scipy-user
>
>
>


text:
# Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming

The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary order insertion-only streams, improving over the state-of-the-art result on counting 4-cycles. Our algorithm computes a (1+ϵ)-approximation by taking three passes over the stream and using space O(m log n/ϵ^2 T^1/3), where m is the number of edges in the graph and T is the number of 4-cycles.

## Authors

• 2 publications
• ### Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

Consider the following gap cycle counting problem in the streaming model...
09/07/2020 ∙ by Sepehr Assadi, et al. ∙ 0

• ### ONCE and ONCE+: Counting the Frequency of Time-constrained Serial Episodes in a Streaming Sequence

As a representative sequential pattern mining problem, counting the freq...
01/29/2018 ∙ by Hui Li, et al. ∙ 0

• ### Model Counting meets F0 Estimation

Constraint satisfaction problems (CSP's) and data stream models are two ...
05/03/2021 ∙ by A. Pavan, et al. ∙ 0

• ### Counting the geodesic cycles of a given length

Assume that X is a connected regular undirected graph of finite order n....
12/24/2019 ∙ by Hau-Wen Huang, et al. ∙ 0

• ### Counting Butterfies from a Large Bipartite Graph Stream

We consider the estimation of properties on massive bipartite graph stre...
12/08/2018 ∙ by Seyed-Vahid Sanei-Mehri, et al. ∙ 0

• ### WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams

If we cannot store all edges in a graph stream, which edges should we st...
09/10/2017 ∙ by Kijung Shin, et al. ∙ 0

• ### Ensembles of Cycles Programmed in GiNaC

This library manipulates ensembles of cycles (quadrics), which are inter...
12/09/2015 ∙ by Vladimir V. Kisil, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Subgraph counting is a fundamental graph problem and an important primitive in massive graph analysis. It has many applications in data mining and analyzing the structure of large networks. This problem has also received a lot of attention in the streaming community, with the main focus on counting triangles [1, 2, 4, 6, 8, 14, 7, 5, 15, 3, 9, 13]. Several papers considered counting larger cycles and cliques [3, 9, 12], and a few studied arbitrary subgraphs of constant size [3, 10, 11]. There is also work on counting 4-cycles in the case when the underlying graph is bipartite [16]. Since a 4-cycle is also a 2-by-2 biclique, it is the most basic motif in bipartite graphs and plays essentially the same role as a triangle does in general graphs.

In this paper, we concentrate on counting 4-cycles in the arbitrary order insertion-only streaming model, improving over the state-of-the-art algorithm presented by McGregor and Vorotnikova [13].

### 1.1 Our Result and Previous Work

Throughout this paper, we use to denote the number of vertices in the graph, to denote the number of edges, and for the number of 4-cycles. Note that our algorithm is parameterized in terms of , which is a convention adopted in the literature. In practice, the quantities in the algorithm would be initialized based on a promised lower bound on .

Our result is as follows.

###### Theorem 1.

There exists an space algorithm that takes three passes over an arbitrary order stream and returns a

multiplicative approximation to the number of 4-cycles in the graph with probability at least

.

By running copies of the algorithm in parallel and taking the median of their outputs, we can increase the success probability to , where .

Our algorithm can be directly compared to the space222We use notation to hide and factors. algorithm by McGregor and Vorotnikova [13]. It takes the same number of passes over the stream and has the same approximation guarantees. We believe that the space of our algorithm is tight, however the best known lower bound is currently  [13].

In [3] Bera and Chakrabarti present a different 4-cycles counting algorithm which takes four passes and uses space . Note, that the space used by our algorithm is as good or better when . McGregor and Vorotnikova [13] also present a 2-pass space algorithm which distinguishes between graphs with 0 and 4-cycles.

## 2 Algorithm and Analysis

### 2.1 Notation

A wedge is a path of length 2. For wedge we call vertices and the endpoints of the wedge and vertex the center.

We use to denote the set of neighbors of vertex . Consider sets of vertices and . Edges between these two sets form a complete bipartite graph, which we call a diamond with endpoints and . We say that wedge is a part of diamond if they have the same endpoints. Note that a diamond with endpoints and consists of wedges and involves 4-cycles.

Throughout the paper we use , , and to denote the number of 4-cycles involving edge , wedge , or involved in diamond respectively. For any quantity , we use

to denote its estimate.

In Section 2.3, we define heavy/light edges, wedges, and diamonds, where “heavy” roughly corresponds to “involved in many 4-cycles” and “light” to “involved in few 4-cycles”. Note that these are defined by the algorithm and depend on the collected samples of vertices and edges. We define to be the number of 4-cycles with at least one heavy wedge and as the number of 4-cycles with no heavy wedges and at most one heavy edge.

### 2.2 Main Idea

The most basic algorithm approximating the number of 4-cycles in a graph is as follows:

Pass 1:

Sample edges with probability , call set .

Pass 2:

For each edge in the stream, let be the number of 3-paths with all edges in that completes to a 4-cycle.

Return:

.

In expectation, the value returned by this algorithm is

. However, due to the fact that some edges or wedges in the graph can be involved in a large number of 4-cycles, the variance of this estimator is large. If an edge or wedge participates in many 4-cycles, call it “bad”. In this paper, we show that it is possible to identify such bad edges and wedges and take care of them separately, leading to an accurate approximation.

We observe that if wedge is bad, then it is a part of a large diamond with endpoints and . If we sample vertices in and collect all incident edges, we will detect the diamond and accurately estimate its size. Using this method, we approximate the total number of cycles with bad wedges.

We then separately approximate the number of cycles with no bad wedges and at most one bad edge. This procedure follows the same template as the arbitrary order 4-cycle counting algorithm in [13]

. Sampling edges uniformly at a certain rate allows us to obtain some 3-paths which are involved in 4-cycles with no bad wedges. Additionally, sampling vertices uniformly and storing all incident edges allows us to build an oracle roughly classifying edges as good or bad. We use this oracle to compute the number of bad edges in each of the cycles we discover. Note that the oracle takes an extra pass over the stream, and thus in total our algorithm uses three passes.

### 2.3 Algorithm

The algorithm in this section computes estimates to and separately and then returns their sum. We later show that is an accurate approximation of .

Within the algorithm, we define heavy/light diamonds and wedges. Roughly speaking, a heavy diamond consist of wedges and a light diamond consist of wedges. A wedge is then defined as heavy or light if it is a part of a heavy or light diamond respectively.

In the third pass, we refer to the oracle which classifies edges as heavy or light. It is described separately after the main algorithm.

Pass 1:
• Let .

• Sample edges with probability , call set .

• Sample vertices with probability , call set . Collect all incident edges, call set .

• Sample vertices with probability , call set . Collect all incident edges, call set .

After Pass 1:
• For a pair of vertices , let be the number of wedges with center in and endpoints and .

• Define diamond with endpoints and to be heavy if and light otherwise. Let .

• Define wedge with endpoints and to be heavy if it is part of a heavy diamond and light otherwise. Let .

• Find all pairs of vertices which are endpoints of heavy diamonds/wedges.

• Let , where is a heavy diamond.

Pass 2:

For every edge in the stream:

• Check if completes any 3 edges from to a 4-cycle (call it ). Check whether has a heavy wedge; if not, store .

Pass 3:
• For all edges involved in cycles stored in pass 2, use to classify them as heavy or light.

• Let be the number of pairs s.t. has no heavy edges.

• Let be the number of pairs s.t. is heavy and the other 3 edges in are light.

• Let

Return:

##### Oracle.

Below, we describe the oracle which classifies edges as heavy or light. Roughly speaking, heavy edges are involved in 4-cycles and light edges in .

Suppose, that we need to classify edge as heavy or light. We then look at edges sharing a vertex with . In the post-processing of the first pass, we determined all pairs of vertices which are endpoints of heavy diamonds/wedges. Thus, for wedge we can refer to that list to check whether it is heavy or not. If it is heavy, we also get an estimate of the number of 4-cycles it is involved in and thus contributes to . Separately, we approximate the total number of 4-cycles on which involve two light wedges and .

oracle(, , ):
• Let and .

• For wedges of the form , where : if is heavy, “exclude”333When we talk about “excluding” edges from , we need to “exclude” different sets of edges for different instances of the oracle. In practice, for each instance mark those edges and ignore them. However, they might be used by other instances. from .

• For each edge in the stream, s.t. shares a vertex with :

• Look up whether is heavy.

• If heavy, .

• If light and , let be the number of vertices , such that is a 4-cycle. .

• Let .

• Return:

### 2.4 Correctness

#### 2.4.1 Oracle

In Lemma 2, we show that light edges are involved in at most 4-cycles and heavy edges are involved in at least cycles. Note that the oracle relies on the procedure estimating the number of 4-cycles on a heavy wedge, so in the proof we refer to Lemma 3 below.

###### Lemma 2.

With high probability

a.

implies

b.

implies

###### Proof.

Let be the number of 4-cycles on , where is a part of a heavy wedge. Let . Let and be our estimates of those two quantities.

Note that in the process of approximating , we are double-counting 4-cycles with two heavy wedges involving . However, we can show that this double-count is negligible. Let be the number of heavy diamonds which involve . Since each 4-cycle can belong to at most 2 diamonds, we are double-counting at most cycles. From Lemma 3 part (b), it follows that the number of 4-cycles in a heavy diamond is at least . Therefore, and . If is sufficiently large, then .

From Lemma 3 part (c) it follows that

 ∑heavy w:e∈wˆt(w)=(1±ϵ/2)∑heavy w:e∈wt(w)

Taking double-counting into account,

 ˆtH(e)=(1±ϵ)tH(e) (1)

Recall that and let be the number of cycles with no heavy wedges if , and otherwise. Let and note that .

If , then , and from the Chernoff bound it follows that

 P[|ˆtL(e)−tL(e)|≥T2/3/4]=P[|XL−ptL(e)|≥pT2/3/4]≤2exp(−16pT2/36T1/3)≤1/poly(n) (2)

where the first inequality follows from the fact that for all . Similarly, if , then

 P[|ˆtL(e)−tL(e)|≥t(e)/4]≤1/poly(n) (3)

We first prove the contrapositive of (a). Assume . Then from Eq. 1 (taking ) and Eq. 3,

 ˆt(e)≥(tH(e)−tH(e)/4)+(tL(e)−t(e)/4)≥t(e)−t(e)/2>T2/3

Similarly, we prove the contrapositive of (b) from Eq. 1 and 2. If , then

 ˆt(e)≤(tH(e)+tH(e)/4)+(tL(e)+T2/3/4)

#### 2.4.2 Estimating Th

In Lemma 3, we prove that we can distinguish between large and small diamonds and estimate the number of 4-cycles in a heavy diamond or on a heavy wedge.

###### Lemma 3.

Let be the number of wedges in diamond , and let be the number of those wedges with center in . Recall that is the number of 4-cycles in diamond , and is the number of 4-cycles involving wedge . Then with high probability,

a.

If diamond is heavy (), then

b.

If diamond is light (), then

c.

If wedge is heavy, then

d.

If diamond is heavy, then

###### Proof.

Observe that . By an application of the Chernoff bound, if , then

 P[q(d)

proving (a). Statement (b) is proved similarly.

Note that the number of 4-cycles in a diamond grows as the square of the number of wedges. Therefore, to get a -approximation to , we need to estimate to a higher accuracy. If , from Chernoff it follows that

 P[|q(d)−w(d)p|≥(ϵ/20)w(d)p]≤2exp(−ϵ2w(d)p/1200)≤1/poly(n)

Recall that if a diamond consists of wedges, then the number of 4-cycles on each of those wedges is . Therefore, statement (c) follows since . Statement (d) follows since and . ∎

###### Lemma 4.

With high probability, .

###### Proof.

First, note that our algorithm double-counts 4-cycles which are involved in two heavy diamonds. As was mentioned before, the number of 4-cycles in a heavy diamond is at least , and thus the number of heavy diamonds is at most . Since two diamonds can have at most one cycle in common, we are double-counting at most cycles. The rest of the proof follows from Lemma 3 part (d). ∎

#### 2.4.3 Estimating Tl

###### Lemma 5.

With constant probability, .

###### Proof.

Let be the number of 4-cycles in with heavy edges. Let and . Note that and .

We now show that with constant probability, and .

By an application of the Chebyshev bound,

 P[|ˆT0−T0|≤ϵT/4]≤1/16

as long as . We now give a bound on the variance of . Let be the set of 3-paths which are involved in 4-cycles in . Let be 1 if all 3 edges of path were sampled and 0 otherwise. Then

 V[ˆT0] =V⎡⎣14p3∑q∈H0Xq⎤⎦ =116p6⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝∑q∈H0V[Xq]+∑q,t∈H0:q≠t,q∩t≠∅COV[Xq,Xt]⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ ≤116p6⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝∑q∈H0E[X2q]+∑q,t∈H0:q≠t,q∩t≠∅E[XqXt]⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ ≤116p6⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝∑q∈H0p3+∑q∈H0∑t∈H0:q≠t,|q∩t|=1p5+∑q∈H0∑t∈H0:q≠t,|q∩t|=2p4⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ ≤116p6⎛⎝|H0|p3+∑q∈H0cT2/3p5+∑q∈H0cT1/3p4⎞⎠ (4) ≤116p6(|H0|p3+c|H0|T2/3p5+c|H0|T1/3p4) ≤T/4p3+cT5/3/4p+cT4/3/4p2 ≤ϵ2T2/256 (5)

Equation 4 follows from the fact that any path intersects at most other paths in at one edge and at most paths at two edges (from Lemmas 2 and 3). Equation 5 follows from our definition of .

Proving follows along the same lines. ∎

#### 2.4.4 Estimating T

We refer to one of the lemmas in [13], which bounds the number of 4-cycles with at most one edge which is involved in a lot of cycles.

###### Lemma 6 (McGregor and Vorotnikova [13]).

We call an edge “bad” if it is contained in at least 4-cycles, and “good” otherwise. There are at least cycles containing no more than one bad edge.

Applying this lemma with , we get that the number of cycles with at most one bad edge is at least . We can now prove the main lemma.

###### Lemma 7.

With constant probability, .

###### Proof.

Let be the number of cycles with at least one heavy wedge and at most one heavy edge. Note that . Since good edges (with ) are classified as light w.h.p.,

 (1−ϵ/6)T≤TL+T′H≤TL+TH≤T

where the first inequality follows from Lemma 6. The rest of the proof follows from Lemmas 4 and 5. ∎

### 2.5 Space analysis

Sets , , and all have the same expected size . The expected number of cycles stored in pass 2 is . Finally, the extra space used by each instance of is in expectation , since it keeps track of a constant number of counters and “excluded” edges, corresponding to heavy wedges involving among the input of the instance. Therefore, the total space used by the algorithm is .

## References

• [1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 5–14, 2012.
• [2] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 623–632, 2002.
• [3] Suman K. Bera and Amit Chakrabarti. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
• [4] Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 244–254, 2013.
• [5] Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, and Rasmus Pagh. Triangle counting in dynamic graph streams. Algorithmica, 76(1):259–278, Sep 2016.
• [6] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 253–262, 2006.
• [7] Graham Cormode and Hossein Jowhari. A second look at counting triangles in graph streams. Theor. Comput. Sci., 552:44–51, 2014.
• [8] Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Proceedings of the 11th International Computing and Combinatorics Conference (COCOON), pages 710–716, 2005.
• [9] John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019., pages 119–133, 2019.
• [10] John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1778–1797, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics.
• [11] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP’12, pages 598–609, Berlin, Heidelberg, 2012. Springer-Verlag.
• [12] Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. Approximate counting of cycles in streams. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 677–688, 2011.
• [13] Andrew McGregor and Sofya Vorotnikova. Triangle and four cycle counting in the data stream model. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, page 445–456, New York, NY, USA, 2020. Association for Computing Machinery.
• [14] Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 401–411, 2016.
• [15] A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. PVLDB, 6(14):1870–1881, 2013.
• [16] Seyed-Vahid Sanei-Mehri, Yu Zhang, Ahmet Erdem Sariyüce, and Srikanta Tirthapura. Fleet: Butterfly estimation from a bipartite graph stream. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, page 1201–1210, New York, NY, USA, 2019. Association for Computing Machinery.


text:
# The Stacks Project

## Tag 0AB8

### 39.14. Finite groupoids

A groupoid scheme $(U, R, s, t, c)$ is sometimes called finite if the morphisms $s$ and $t$ are finite. This is potentially confusing as it doesn't imply that $U$ or $R$ or the quotient sheaf $U/R$ are finite over anything.

Lemma 39.14.1. Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$ are finite. There exists a sequence of $R$-invariant closed subschemes $$U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$$ such that $\bigcap Z_r = \emptyset$ and such that $s^{-1}(Z_{r - 1}) \setminus s^{-1}(Z_r) \to Z_{r - 1} \setminus Z_r$ is finite locally free of rank $r$.

Proof. Let $\{Z_r\}$ be the stratification of $U$ given by the Fitting ideals of the finite type quasi-coherent modules $s_*\mathcal{O}_R$. See Divisors, Lemma 30.9.6. Since the identity $e : U \to R$ is a section to $s$ we see that $s_*\mathcal{O}_R$ contains $\mathcal{O}_S$ as a direct summand. Hence $U = Z_{-1} = Z_0$ (details omitted). Since formation of Fitting ideals commutes with base change (More on Algebra, Lemma 15.8.4) we find that $s^{-1}(Z_r)$ corresponds to the $r$th Fitting ideal of $\text{pr}_{1, *}\mathcal{O}_{R \times_{s, U, t} R}$ because the lower right square of diagram (39.3.0.1) is cartesian. Using the fact that the lower left square is also cartesian we conclude that $s^{-1}(Z_r) = t^{-1}(Z_r)$, in other words $Z_r$ is $R$-invariant. The morphism $s^{-1}(Z_{r - 1}) \setminus s^{-1}(Z_r) \to Z_{r - 1} \setminus Z_r$ is finite locally free of rank $r$ because the module $s_*\mathcal{O}_R$ pulls back to a finite locally free module of rank $r$ on $Z_{r - 1} \setminus Z_r$ by Divisors, Lemma 30.9.6. $\square$

Lemma 39.14.2. Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$ are finite. There exists an open subscheme $W \subset U$ and a closed subscheme $W' \subset W$ such that

1. $W$ and $W'$ are $R$-invariant,
2. $U = t(s^{-1}(\overline{W}))$ set theoretically,
3. $W$ is a thickening of $W'$, and
4. the maps $s'$, $t'$ of the restriction $(W', R', s', t', c')$ are finite locally free.

Proof. Consider the stratification $U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$ of Lemma 39.14.1.

We will construct disjoint unions $W = \coprod_{r \geq 1} W_r$ and $W' = \coprod_{r \geq 1} W'_r$ with each $W'_r \to W_r$ a thickening of $R$-invariant subschemes of $U$ such that the morphisms $s_r', t_r'$ of the restrictions $(W_r', R_r', s_r', t_r', c_r')$ are finite locally free of rank $r$. To begin we set $W_1 = W'_1 = U \setminus Z_1$. This is an $R$-invariant open subscheme of $U$, it is true that $W_0$ is a thickening of $W'_0$, and the maps $s_1'$, $t_1'$ of the restriction $(W_1', R_1', s_1', t_1', c_1')$ are isomorphisms, i.e., finite locally free of rank $1$. Moreover, every point of $U \setminus Z_1$ is in $t(s^{-1}(\overline{W_1}))$.

Assume we have found subschemes $W'_r \subset W_r \subset U$ for $r \leq n$ such that

1. $W_1, \ldots, W_n$ are disjoint,
2. $W_r$ and $W_r'$ are $R$-invariant,
3. $U \setminus Z_n \subset \bigcup_{r \leq n} t(s^{-1}(\overline{W_r}))$ set theoretically,
4. $W_r$ is a thickening of $W'_r$,
5. the maps $s_r'$, $t_r'$ of the restriction $(W_r', R_r', s_r', t_r', c_r')$ are finite locally free of rank $r$.

Then we set $$W_{n + 1} = Z_n \setminus \left( Z_{n + 1} \cup \bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r})) \right)$$ set theoretically and $$W'_{n + 1} = Z_n \setminus \left( Z_{n + 1} \cup \bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r})) \right)$$ scheme theoretically. Then $W_{n + 1}$ is an $R$-invariant open subscheme of $U$ because $Z_{n + 1} \setminus \overline{U \setminus Z_{n + 1}}$ is open in $U$ and $\overline{U \setminus Z_{n + 1}}$ is contained in the closed subset $\bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r}))$ we are removing by property (3) and the fact that $t$ is a closed morphism. It is clear that $W'_{n + 1}$ is a closed subscheme of $W_{n + 1}$ with the same underlying topological space. Finally, properties (1), (2) and (3) are clear and property (5) follows from Lemma 39.14.1.

By Lemma 39.14.1 we have $\bigcap Z_r = \emptyset$. Hence every point of $U$ is contained in $U \setminus Z_n$ for some $n$. Thus we see that $U = \bigcup_{r \geq 1} t(s^{-1}(\overline{W_r}))$ set theoretically and we see that (2) holds. Thus $W' \subset W$ satisfy (1), (2), (3), and (4). $\square$

Let $(U, R, s, t, c)$ be a groupoid scheme. Given a point $u \in U$ the $R$-orbit of $u$ is the subset $t(s^{-1}(\{u\}))$ of $U$.

Lemma 39.14.3. In Lemma 39.14.2 assume in addition that $s$ and $t$ are of finite presentation. Then

1. the morphism $W' \to W$ is of finite presentation, and
2. if $u \in U$ is a point whose $R$-orbit consists of generic points of irreducible components of $U$, then $u \in W$.

Proof. In this case the stratification $U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$ of Lemma 39.14.1 is given by closed immersions $Z_k \to U$ of finite presentation, see Divisors, Lemma 30.9.6. Part (1) follows immediately from this as $W' \to W$ is locally given by intersecting the open $W$ by $Z_r$. To see part (2) let $\{u_1, \ldots, u_n\}$ be the orbit of $u$. Since the closed subschemes $Z_k$ are $R$-invariant and $\bigcap Z_k = \emptyset$, we find an $k$ such that $u_i \in Z_k$ and $u_i \not \in Z_{k + 1}$ for all $i$. The image of $Z_k \to U$ and $Z_{k + 1} \to U$ is locally constructible (Morphisms, Theorem 28.21.3). Since $u_i \in U$ is a generic point of an irreducible component of $U$, there exists an open neighbourhood $U_i$ of $u_i$ which is contained in $Z_k \setminus Z_{k + 1}$ set theoretically (Properties, Lemma 27.2.2). In the proof of Lemma 39.14.2 we have constructed $W$ as a disjoint union $\coprod W_r$ with $W_r \subset Z_{r - 1} \setminus Z_r$ such that $U = \bigcup t(s^{-1}(\overline{W_r}))$. As $\{u_1, \ldots, u_n\}$ is an $R$-orbit we see that $u \in t(s^{-1}(\overline{W_r}))$ implies $u_i \in \overline{W_r}$ for some $i$ which implies $U_i \cap W_r \not = \emptyset$ which implies $r = k$. Thus we conclude that $u$ is in $$W_{k + 1} = Z_k \setminus \left( Z_{k + 1} \cup \bigcup\nolimits_{r \leq k} t(s^{-1}(\overline{W_r})) \right)$$ as desired. $\square$

Lemma 39.14.4. Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$ are finite and of finite presentation and $U$ quasi-separated. Let $u_1, \ldots, u_m \in U$ be points whose orbits consist of generic points of irreducible components of $U$. Then there exist $R$-invariant subschemes $V' \subset V \subset U$ such that

1. $u_1, \ldots, u_m \in V'$,
2. $V$ is open in $U$,
3. $V'$ and $V$ are affine,
4. $V' \subset V$ is a thickening of finite presentation,
5. the morphisms $s', t'$ of the restriction $(V', R', s', t', c')$ are finite locally free.

Proof. Let $W' \subset W \subset U$ be as in Lemma 39.14.2. By Lemma 39.14.3 we get $u_j \in W$ and that $W' \to W$ is a thickening of finite presentation. By Limits, Lemma 31.11.3 it suffices to find an $R$-invariant affine open subscheme $V'$ of $W'$ containing $u_j$ (because then we can let $V \subset W$ be the corresponding open subscheme which will be affine). Thus we may replace $(U, R, s, t, c)$ by the restriction $(W', R', s', t', c')$ to $W'$. In other words, we may assume we have a groupoid scheme $(U, R, s, t, c)$ whose morphisms $s$ and $t$ are finite locally free. By Properties, Lemma 27.29.1 we can find an affine open containing the union of the orbits of $u_1, \ldots, u_m$. Finally, we can apply Groupoids, Lemma 38.24.1 to conclude. $\square$

The following lemma is a special case of Lemma 39.14.4 but we redo the argument as it is slightly easier in this case (it avoids using Lemma 39.14.3).

Lemma 39.14.5. Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$ finite, $U$ is locally Noetherian, and $u_1, \ldots, u_m \in U$ points whose orbits consist of generic points of irreducible components of $U$. Then there exist $R$-invariant subschemes $V' \subset V \subset U$ such that

1. $u_1, \ldots, u_m \in V'$,
2. $V$ is open in $U$,
3. $V'$ and $V$ are affine,
4. $V' \subset V$ is a thickening,
5. the morphisms $s', t'$ of the restriction $(V', R', s', t', c')$ are finite locally free.

Proof. Let $\{u_{j1}, \ldots, u_{jn_j}\}$ be the orbit of $u_j$. Let $W' \subset W \subset U$ be as in Lemma 39.14.2. Since $U = t(s^{-1}(\overline{W}))$ we see that at least one $u_{ji} \in \overline{W}$. Since $u_{ji}$ is a generic point of an irreducible component and $U$ locally Noetherian, this implies that $u_{ji} \in W$. Since $W$ is $R$-invariant, we conclude that $u_j \in W$ and in fact the whole orbit is contained in $W$. By Cohomology of Schemes, Lemma 29.13.3 it suffices to find an $R$-invariant affine open subscheme $V'$ of $W'$ containing $u_1, \ldots, u_m$ (because then we can let $V \subset W$ be the corresponding open subscheme which will be affine). Thus we may replace $(U, R, s, t, c)$ by the restriction $(W', R', s', t', c')$ to $W'$. In other words, we may assume we have a groupoid scheme $(U, R, s, t, c)$ whose morphisms $s$ and $t$ are finite locally free. By Properties, Lemma 27.29.1 we can find an affine open containing $\{u_{ij}\}$ (a locally Noetherian scheme is quasi-separated by Properties, Lemma 27.5.4). Finally, we can apply Groupoids, Lemma 38.24.1 to conclude. $\square$

Lemma 39.14.6. Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$ with $s, t$ integral. Let $g : U' \to U$ be an integral morphism such that every $R$-orbit in $U$ meets $g(U')$. Let $(U', R', s', t', c')$ be the restriction of $R$ to $U'$. If $u' \in U'$ is contained in an $R'$-invariant affine open, then the image $u \in U$ is contained in an $R$-invariant affine open of $U$.

Proof. Let $W' \subset U'$ be an $R'$-invariant affine open. Set $\tilde R = U' \times_{g, U, t} R$ with maps $\text{pr}_0 : \tilde R \to U'$ and $h = s \circ \text{pr}_1 : \tilde R \to U$. Observe that $\text{pr}_0$ and $h$ are integral. It follows that $\tilde W = \text{pr}_0^{-1}(W')$ is affine. Since $W'$ is $R'$-invariant, the image $W = h(\tilde W)$ is set theoretically $R$-invariant and $\tilde W = h^{-1}(W)$ set theoretically (details omitted). Thus, if we can show that $W$ is open, then $W$ is a scheme and the morphism $\tilde W \to W$ is integral surjective which implies that $W$ is affine by Limits, Proposition 31.11.2. However, our assumption on orbits meeting $U'$ implies that $h : \tilde R \to U$ is surjective. Since an integral surjective morphism is submersive (Topology, Lemma 5.6.5 and Morphisms, Lemma 28.42.7) it follows that $W$ is open. $\square$

The following technical lemma produces ''almost'' invariant functions in the situation of a finite groupoid on a quasi-affine scheme.

Lemma 39.14.7. Let $(U, R, s, t, c)$ be a groupoid scheme with $s, t$ finite and of finite presentation. Let $u_1, \ldots, u_m \in U$ be points whose $R$-orbits consist of generic points of irreducible components of $U$. Let $j : U \to \mathop{\rm Spec}(A)$ be an immersion. Let $I \subset A$ be an ideal such that $j(U) \cap V(I) = \emptyset$ and $V(I) \cup j(U)$ is closed in $\mathop{\rm Spec}(A)$. Then there exists an $h \in I$ such that $j^{-1}D(h)$ is an $R$-invariant affine open subscheme of $U$ containing $u_1, \ldots, u_m$.

Proof. Let $u_1, \ldots, u_m \in V' \subset V \subset U$ be as in Lemma 39.14.4. Since $U \setminus V$ is closed in $U$, $j$ an immersion, and $V(I) \cup j(U)$ is closed in $\mathop{\rm Spec}(A)$, we can find an ideal $J \subset I$ such that $V(J) = V(I) \cup j(U \setminus V)$. For example we can take the ideal of elements of $I$ which vanish on $j(U \setminus V)$. Thus we can replace $(U, R, s, t, c)$, $j : U \to \mathop{\rm Spec}(A)$, and $I$ by $(V', R', s', t', c')$, $j|_{V'} : V' \to \mathop{\rm Spec}(A)$, and $J$. In other words, we may assume that $U$ is affine and that $s$ and $t$ are finite locally free. Take any $f \in I$ which does not vanish at all the points in the $R$-orbits of $u_1, \ldots, u_m$ (Algebra, Lemma 10.14.2). Consider $$g = \text{Norm}_s(t^\sharp(j^\sharp(f))) \in \Gamma(U, \mathcal{O}_U)$$ Since $f \in I$ and since $V(I) \cup j(U)$ is closed we see that $U \cap D(f) \to D(f)$ is a closed immersion. Hence $f^ng$ is the image of an element $h \in I$ for some $n > 0$. We claim that $h$ works. Namely, we have seen in Groupoids, Lemma 38.23.2 that $g$ is an $R$-invariant function, hence $D(g) \subset U$ is $R$-invariant. Since $f$ does not vanish on the orbit of $u_j$, the function $g$ does not vanish at $u_j$. Moreover, we have $V(g) \supset V(j^\sharp(f))$ and hence $j^{-1}D(h) = D(g)$. $\square$

Lemma 39.14.8. Let $(U, R, s, t, c)$ be a groupoid scheme. If $s, t$ are finite, and $u, u' \in R$ are distinct points in the same orbit, then $u'$ is not a specialization of $u$.

Proof. Let $r \in R$ with $s(r) = u$ and $t(r) = u'$. If $u \leadsto u'$ then we can find a nontrivial specialization $r \leadsto r'$ with $s(r') = u'$, see Schemes, Lemma 25.19.8. Set $u'' = t(r')$. Note that $u'' \not = u'$ as there are no specializations in the fibres of a finite morphism. Hence we can continue and find a nontrivial specialization $r' \leadsto r''$ with $s(r'') = u''$, etc. This shows that the orbit of $u$ contains an infinite sequence $u \leadsto u' \leadsto u'' \leadsto \ldots$ of specializations which is nonsense as the orbit $t(s^{-1}(\{u\}))$ is finite. $\square$

Lemma 39.14.9. Let $j : V \to \mathop{\rm Spec}(A)$ be a quasi-compact immersion of schemes. Let $f \in A$ be such that $j^{-1}D(f)$ is affine and $j(V) \cap V(f)$ is closed. Then $V$ is affine.

Proof. This follows from Morphisms, Lemma 28.11.14 but we will also give a direct proof. Let $A' = \Gamma(V, \mathcal{O}_V)$. Then $j' : V \to \mathop{\rm Spec}(A')$ is a quasi-compact open immersion, see Properties, Lemma 27.18.3. Let $f' \in A'$ be the image of $f$. Then $(j')^{-1}D(f') = j^{-1}D(f)$ is affine. On the other hand, $j'(V) \cap V(f')$ is a subscheme of $\mathop{\rm Spec}(A')$ which maps isomorphically to the closed subscheme $j(V) \cap V(f)$ of $\mathop{\rm Spec}(A)$. Hence it is closed in $\mathop{\rm Spec}(A')$ for example by Schemes, Lemma 25.21.12. Thus we may replace $A$ by $A'$ and assume that $j$ is an open immersion and $A = \Gamma(V, \mathcal{O}_V)$.

In this case we claim that $j(V) = \mathop{\rm Spec}(A)$ which finishes the proof. If not, then we can find a principal affine open $D(g) \subset \mathop{\rm Spec}(A)$ which meets the complement and avoids the closed subset $j(V) \cap V(f)$. Note that $j$ maps $j^{-1}D(f)$ isomorphically onto $D(f)$, see Properties, Lemma 27.18.2. Hence $D(g)$ meets $V(f)$. On the other hand, $j^{-1}D(g)$ is a principal open of the affine open $j^{-1}D(f)$ hence affine. Hence by Properties, Lemma 27.18.2 again we see that $D(g)$ is isomorphic to $j^{-1}D(g) \subset j^{-1}D(f)$ which implies that $D(g) \subset D(f)$. This contradiction finishes the proof. $\square$

Lemma 39.14.10. Let $(U, R, s, t, c)$ be a groupoid scheme. Let $u \in U$. Assume

1. $s, t$ are finite morphisms,
2. $U$ is separated and locally Noetherian,
3. $\dim(\mathcal{O}_{U, u'}) \leq 1$ for every point $u'$ in the orbit of $u$.

Then $u$ is contained in an $R$-invariant affine open of $U$.

Proof. The $R$-orbit of $u$ is finite. By conditions (2) and (3) it is contained in an affine open $U'$ of $U$, see Varieties, Proposition 32.41.7. Then $t(s^{-1}(U \setminus U'))$ is an $R$-invariant closed subset of $U$ which does not contain $u$. Thus $U \setminus t(s^{-1}(U \setminus U'))$ is an $R$-invariant open of $U'$ containing $u$. Replacing $U$ by this open we may assume $U$ is quasi-affine.

By Lemma 39.14.6 we may replace $U$ by its reduction and assume $U$ is reduced. This means $R$-invariant subschemes $W' \subset W \subset U$ of Lemma 39.14.2 are equal $W' = W$. As $U = t(s^{-1}(\overline{W}))$ some point $u'$ of the $R$-orbit of $u$ is contained in $\overline{W}$ and by Lemma 39.14.6 we may replace $U$ by $\overline{W}$ and $u$ by $u'$. Hence we may assume there is a dense open $R$-invariant subscheme $W \subset U$ such that the morphisms $s_W, t_W$ of the restriction $(W, R_W, s_W, t_W, c_W)$ are finite locally free.

If $u \in W$ then we are done by Groupoids, Lemma 38.24.1 (because $W$ is quasi-affine so any finite set of points of $W$ is contained in an affine open, see Properties, Lemma 27.29.5). Thus we assume $u \not \in W$ and hence none of the points of the orbit of $u$ is in $W$. Let $\xi \in U$ be a point with a nontrivial specialization to a point $u'$ in the orbit of $u$. Since there are no specializations among the points in the orbit of $u$ (Lemma 39.14.8) we see that $\xi$ is not in the orbit. By assumption (3) we see that $\xi$ is a generic point of $U$ and hence $\xi \in W$. As $U$ is Noetherian there are finitely many of these points $\xi_1, \ldots, \xi_m \in W$. Because $s_W, t_W$ are flat the orbit of each $\xi_j$ consists of generic points of irreducible components of $W$ (and hence $U$).

Let $j : U \to \mathop{\rm Spec}(A)$ be an immersion of $U$ into an affine scheme (this is possible as $U$ is quasi-affine). Let $J \subset A$ be an ideal such that $V(J) \cap j(W) = \emptyset$ and $V(J) \cup j(W)$ is closed. Apply Lemma 39.14.7 to the groupoid scheme $(W, R_W, s_W, t_W, c_W)$, the morphism $j|_W : W \to \mathop{\rm Spec}(A)$, the points $\xi_j$, and the ideal $J$ to find an $f \in J$ such that $(j|_W)^{-1}D(f)$ is an $R_W$-invariant affine open containing $\xi_j$ for all $j$. Since $f \in J$ we see that $j^{-1}D(f) \subset W$, i.e., $j^{-1}D(f)$ is an $R$-invariant affine open of $U$ contained in $W$ containing all $\xi_j$.

Let $Z$ be the reduced induced closed subscheme structure on $$U \setminus j^{-1}D(f) = j^{-1}V(f).$$ Then $Z$ is set theoretically $R$-invariant (but it may not be scheme theoretically $R$-invariant). Let $(Z, R_Z, s_Z, t_Z, c_Z)$ be the restriction of $R$ to $Z$. Since $Z \to U$ is finite, it follows that $s_Z$ and $t_Z$ are finite. Since $u \in Z$ the orbit of $u$ is in $Z$ and agrees with the $R_Z$-orbit of $u$ viewed as a point of $Z$. Since $\dim(\mathcal{O}_{U, u'}) \leq 1$ and since $\xi_j \not \in Z$ for all $j$, we see that $\dim(\mathcal{O}_{Z, u'}) \leq 0$ for all $u'$ in the orbit of $u$. In other words, the $R_Z$-orbit of $u$ consists of generic points of irreducible components of $Z$.

Let $I \subset A$ be an ideal such that $V(I) \cap j(U) =\emptyset$ and $V(I) \cup j(U)$ is closed. Apply Lemma 39.14.7 to the groupoid scheme $(Z, R_Z, s_Z, t_Z, c_Z)$, the restriction $j|_Z$, the ideal $I$, and the point $u \in Z$ to obtain $h \in I$ such that $j^{-1}D(h) \cap Z$ is an $R_Z$-invariant open affine containing $u$.

Consider the $R_W$-invariant (Groupoids, Lemma 38.23.2) function $$g = \text{Norm}_{s_W}(t_W^\sharp(j^\sharp(h)|_W)) \in \Gamma(W, \mathcal{O}_W)$$ (In the following we only need the restriction of $g$ to $j^{-1}D(f)$ and in this case the norm is along a finite locally free morphism of affines.) We claim that $$V = (W_g \cap j^{-1}D(f)) \cup (j^{-1}D(h) \cap Z)$$ is an $R$-invariant affine open of $U$ which finishes the proof of the lemma. It is set theoretically $R$-invariant by construction. As $V$ is a constuctible set, to see that it is open it suffices to show it is closed under generalization in $U$ (Topology, Lemma 5.19.9 or the more general Topology, Lemma 5.23.5). Since $W_g \cap j^{-1}D(f)$ is open in $U$, it suffices to consider a specialization $u_1 \leadsto u_2$ of $U$ with $u_2 \in j^{-1}D(h) \cap Z$. This means that $h$ is nonzero in $j(u_2)$ and $u_2 \in Z$. If $u_1 \in Z$, then $j(u_1) \leadsto j(u_2)$ and since $h$ is nonzero in $j(u_2)$ it is nonzero in $j(u_1)$ which implies $u_1 \in V$. If $u_1 \not \in Z$ and also not in $W_g \cap j^{-1}D(f)$, then $u_1 \in W$, $u_1 \not \in W_g$ because the complement of $Z = j^{-1}V(f)$ is contained in $W \cap j^{-1}D(f)$. Hence there exists a point $r_1 \in R$ with $s(r_1) = u_1$ such that $h$ is zero in $t(r_1)$. Since $s$ is finite we can find a specialization $r_1 \leadsto r_2$ with $s(r_2) = u_2$. However, then we conclude that $f$ is zero in $u'_2 = t(r_2)$ which contradicts the fact that $j^{-1}D(h) \cap Z$ is $R$-invariant and $u_2$ is in it. Thus $V$ is open.

Observe that $V \subset j^{-1}D(h)$ for our function $h \in I$. Thus we obtain an immersion $$j' : V \longrightarrow \mathop{\rm Spec}(A_h)$$ Let $f' \in A_h$ be the image of $f$. Then $(j')^{-1}D(f')$ is the principal open determined by $g$ in the affine open $j^{-1}D(f)$ of $U$. Hence $(j')^{-1}D(f)$ is affine. Finally, $j'(V) \cap V(f') = j'(j^{-1}D(h) \cap Z)$ is closed in $\mathop{\rm Spec}(A_h/(f')) = \mathop{\rm Spec}((A/f)_h) = D(h) \cap V(f)$ by our choice of $h \in I$ and the ideal $I$. Hence we can apply Lemma 39.14.9 to conclude that $V$ is affine as claimed above. $\square$

The code snippet corresponding to this tag is a part of the file more-groupoids.tex and is located in lines 2412–2957 (see updates for more information).

\section{Finite groupoids}
\label{section-finite-groupoids}

\noindent
A groupoid scheme $(U, R, s, t, c)$ is sometimes called {\it finite} if the
morphisms $s$ and $t$ are finite. This is potentially confusing as it doesn't
imply that $U$ or $R$ or the quotient sheaf $U/R$ are finite over anything.

\begin{lemma}
\label{lemma-finite-stratify}
Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$
are finite. There exists a sequence of $R$-invariant closed subschemes
$$U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$$
such that $\bigcap Z_r = \emptyset$ and such that
$s^{-1}(Z_{r - 1}) \setminus s^{-1}(Z_r) \to Z_{r - 1} \setminus Z_r$
is finite locally free of rank $r$.
\end{lemma}

\begin{proof}
Let $\{Z_r\}$ be the stratification of $U$ given by the Fitting ideals
of the finite type quasi-coherent modules $s_*\mathcal{O}_R$. See
Divisors, Lemma \ref{divisors-lemma-locally-free-rank-r-pullback}.
Since the identity $e : U \to R$ is a section to $s$ we see that
$s_*\mathcal{O}_R$ contains $\mathcal{O}_S$ as a direct summand.
Hence $U = Z_{-1} = Z_0$ (details omitted).
Since formation of Fitting ideals commutes with base change
(More on Algebra, Lemma \ref{more-algebra-lemma-fitting-ideal-basics})
we find that $s^{-1}(Z_r)$ corresponds to the $r$th Fitting ideal
of $\text{pr}_{1, *}\mathcal{O}_{R \times_{s, U, t} R}$ because
the lower right square of diagram (\ref{equation-diagram}) is cartesian.
Using the fact that the lower left square is also cartesian we conclude
that $s^{-1}(Z_r) = t^{-1}(Z_r)$, in other words $Z_r$ is $R$-invariant.
The morphism
$s^{-1}(Z_{r - 1}) \setminus s^{-1}(Z_r) \to Z_{r - 1} \setminus Z_r$
is finite locally free of rank $r$ because the module
$s_*\mathcal{O}_R$ pulls back to a finite locally free module of rank $r$
on $Z_{r - 1} \setminus Z_r$ by
Divisors, Lemma \ref{divisors-lemma-locally-free-rank-r-pullback}.
\end{proof}

\begin{lemma}
\label{lemma-finite-flat-over-almost-dense-subscheme}
Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$
are finite. There exists an open subscheme $W \subset U$ and a closed
subscheme $W' \subset W$ such that
\begin{enumerate}
\item $W$ and $W'$ are $R$-invariant,
\item $U = t(s^{-1}(\overline{W}))$ set theoretically,
\item $W$ is a thickening of $W'$, and
\item the maps $s'$, $t'$ of the restriction $(W', R', s', t', c')$
are finite locally free.
\end{enumerate}
\end{lemma}

\begin{proof}
Consider the stratification $U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$
of Lemma \ref{lemma-finite-stratify}.

\medskip\noindent
We will construct disjoint unions $W = \coprod_{r \geq 1} W_r$ and
$W' = \coprod_{r \geq 1} W'_r$ with each $W'_r \to W_r$ a thickening
of $R$-invariant subschemes of $U$ such that the morphisms
$s_r', t_r'$ of the restrictions $(W_r', R_r', s_r', t_r', c_r')$
are finite locally free of rank $r$. To begin we set
$W_1 = W'_1 = U \setminus Z_1$. This is an $R$-invariant open
subscheme of $U$, it is true that $W_0$ is a thickening of $W'_0$,
and the maps $s_1'$, $t_1'$ of the
restriction $(W_1', R_1', s_1', t_1', c_1')$ are isomorphisms, i.e.,
finite locally free of rank $1$.
Moreover, every point of $U \setminus Z_1$ is in $t(s^{-1}(\overline{W_1}))$.

\medskip\noindent
Assume we have found subschemes $W'_r \subset W_r \subset U$ for $r \leq n$
such that
\begin{enumerate}
\item $W_1, \ldots, W_n$ are disjoint,
\item $W_r$ and $W_r'$ are $R$-invariant,
\item $U \setminus Z_n \subset \bigcup_{r \leq n} t(s^{-1}(\overline{W_r}))$
set theoretically,
\item $W_r$ is a thickening of $W'_r$,
\item the maps $s_r'$, $t_r'$ of the restriction
$(W_r', R_r', s_r', t_r', c_r')$ are finite locally free of rank $r$.
\end{enumerate}
Then we set
$$W_{n + 1} = Z_n \setminus \left( Z_{n + 1} \cup \bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r})) \right)$$
set theoretically and
$$W'_{n + 1} = Z_n \setminus \left( Z_{n + 1} \cup \bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r})) \right)$$
scheme theoretically. Then $W_{n + 1}$ is an $R$-invariant open subscheme
of $U$ because $Z_{n + 1} \setminus \overline{U \setminus Z_{n + 1}}$
is open in $U$ and $\overline{U \setminus Z_{n + 1}}$ is contained
in the closed subset $\bigcup\nolimits_{r \leq n} t(s^{-1}(\overline{W_r}))$
we are removing by property (3) and the fact that $t$ is a closed morphism.
It is clear that $W'_{n + 1}$ is a closed subscheme
of $W_{n + 1}$ with the same underlying topological space.
Finally, properties (1), (2) and (3) are clear and property (5) follows from
Lemma \ref{lemma-finite-stratify}.

\medskip\noindent
By Lemma \ref{lemma-finite-stratify} we have $\bigcap Z_r = \emptyset$.
Hence every point of $U$ is contained in $U \setminus Z_n$
for some $n$. Thus we see that
$U = \bigcup_{r \geq 1} t(s^{-1}(\overline{W_r}))$
set theoretically and we see that (2) holds.
Thus $W' \subset W$ satisfy (1), (2), (3), and (4).
\end{proof}

\noindent
Let $(U, R, s, t, c)$ be a groupoid scheme. Given a point $u \in U$
the {\it $R$-orbit} of $u$ is the subset $t(s^{-1}(\{u\}))$ of $U$.

\begin{lemma}
In Lemma \ref{lemma-finite-flat-over-almost-dense-subscheme}
assume in addition that $s$ and $t$ are of finite presentation.
Then
\begin{enumerate}
\item the morphism $W' \to W$ is of finite presentation, and
\item if $u \in U$ is a point whose $R$-orbit consists of
generic points of irreducible components of $U$, then $u \in W$.
\end{enumerate}
\end{lemma}

\begin{proof}
In this case the stratification
$U = Z_0 \supset Z_1 \supset Z_2 \supset \ldots$ of
Lemma \ref{lemma-finite-stratify} is given by closed immersions $Z_k \to U$
of finite presentation, see
Divisors, Lemma \ref{divisors-lemma-locally-free-rank-r-pullback}.
Part (1) follows immediately from this as $W' \to W$ is locally given
by intersecting the open $W$ by $Z_r$. To see part (2)
let $\{u_1, \ldots, u_n\}$ be the orbit of $u$.
Since the closed subschemes $Z_k$ are $R$-invariant and
$\bigcap Z_k = \emptyset$, we find an $k$ such that $u_i \in Z_k$
and $u_i \not \in Z_{k + 1}$ for all $i$.
The image of $Z_k \to U$ and $Z_{k + 1} \to U$ is locally constructible
(Morphisms, Theorem \ref{morphisms-theorem-chevalley}).
Since $u_i \in U$ is a generic point of an irreducible component
of $U$, there exists an open neighbourhood $U_i$ of $u_i$ which
is contained in $Z_k \setminus Z_{k + 1}$ set theoretically
(Properties, Lemma \ref{properties-lemma-generic-point-in-constructible}).
In the proof of Lemma \ref{lemma-finite-flat-over-almost-dense-subscheme}
we have constructed $W$ as a disjoint union $\coprod W_r$
with $W_r \subset Z_{r - 1} \setminus Z_r$ such that
$U = \bigcup t(s^{-1}(\overline{W_r}))$. As $\{u_1, \ldots, u_n\}$
is an $R$-orbit we see that $u \in t(s^{-1}(\overline{W_r}))$
implies $u_i \in \overline{W_r}$ for some $i$ which implies
$U_i \cap W_r \not = \emptyset$ which implies $r = k$.
Thus we conclude that $u$ is in
$$W_{k + 1} = Z_k \setminus \left( Z_{k + 1} \cup \bigcup\nolimits_{r \leq k} t(s^{-1}(\overline{W_r})) \right)$$
as desired.
\end{proof}

\begin{lemma}
\label{lemma-invariant-affine-open-around-generic-point}
Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$. Assume $s, t$
are finite and of finite presentation and $U$ quasi-separated. Let
$u_1, \ldots, u_m \in U$ be points whose orbits consist of generic points
of irreducible components of $U$. Then there exist $R$-invariant subschemes
$V' \subset V \subset U$ such that
\begin{enumerate}
\item $u_1, \ldots, u_m \in V'$,
\item $V$ is open in $U$,
\item $V'$ and $V$ are affine,
\item $V' \subset V$ is a thickening of finite presentation,
\item the morphisms $s', t'$ of the restriction $(V', R', s', t', c')$
are finite locally free.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $W' \subset W \subset U$ be as in
Lemma \ref{lemma-finite-flat-over-almost-dense-subscheme}.
we get $u_j \in W$ and that $W' \to W$ is a thickening of finite presentation.
By Limits, Lemma \ref{limits-lemma-affines-glued-in-closed-affine}
it suffices to find an $R$-invariant affine open subscheme
$V'$ of $W'$ containing $u_j$ (because then we can let $V \subset W$
be the corresponding open subscheme which will be affine).
Thus we may replace $(U, R, s, t, c)$ by the restriction
$(W', R', s', t', c')$ to $W'$.
In other words, we may assume we have a groupoid scheme $(U, R, s, t, c)$
whose morphisms $s$ and $t$ are finite locally free.
By Properties, Lemma \ref{properties-lemma-maximal-points-affine}
we can find an affine open containing the union of the orbits of
$u_1, \ldots, u_m$. Finally, we can apply
Groupoids, Lemma \ref{groupoids-lemma-find-invariant-affine}
to conclude.
\end{proof}

\noindent
The following lemma is a special case of
Lemma \ref{lemma-invariant-affine-open-around-generic-point}
but we redo the argument as it is slightly easier in this case
(it avoids using

\begin{lemma}
\label{lemma-invariant-affine-open-around-generic-point-Noetherian}
Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$.
Assume $s, t$ finite, $U$ is locally Noetherian, and $u_1, \ldots, u_m \in U$
points whose orbits consist of generic points of irreducible
components of $U$. Then there exist $R$-invariant subschemes
$V' \subset V \subset U$ such that
\begin{enumerate}
\item $u_1, \ldots, u_m \in V'$,
\item $V$ is open in $U$,
\item $V'$ and $V$ are affine,
\item $V' \subset V$ is a thickening,
\item the morphisms $s', t'$ of the restriction $(V', R', s', t', c')$
are finite locally free.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\{u_{j1}, \ldots, u_{jn_j}\}$ be the orbit of $u_j$.
Let $W' \subset W \subset U$ be as in
Lemma \ref{lemma-finite-flat-over-almost-dense-subscheme}.
Since $U = t(s^{-1}(\overline{W}))$ we see that at least
one $u_{ji} \in \overline{W}$. Since $u_{ji}$ is a generic point
of an irreducible component and $U$ locally Noetherian,
this implies that $u_{ji} \in W$. Since $W$ is $R$-invariant, we
conclude that $u_j \in W$ and in fact the whole orbit is contained in $W$.
By Cohomology of Schemes, Lemma
\ref{coherent-lemma-image-affine-finite-morphism-affine-Noetherian}
it suffices to find an $R$-invariant affine open subscheme $V'$
of $W'$ containing $u_1, \ldots, u_m$ (because then we can let $V \subset W$
be the corresponding open subscheme which will be affine).
Thus we may replace $(U, R, s, t, c)$
by the restriction $(W', R', s', t', c')$ to $W'$.
In other words, we may assume we have a groupoid scheme $(U, R, s, t, c)$
whose morphisms $s$ and $t$ are finite locally free.
By Properties, Lemma \ref{properties-lemma-maximal-points-affine}
we can find an affine open containing $\{u_{ij}\}$
(a locally Noetherian scheme is quasi-separated by
Properties, Lemma \ref{properties-lemma-locally-Noetherian-quasi-separated}).
Finally, we can apply
Groupoids, Lemma \ref{groupoids-lemma-find-invariant-affine}
to conclude.
\end{proof}

\begin{lemma}
\label{lemma-find-affine-integral}
Let $(U, R, s, t, c)$ be a groupoid scheme over a scheme $S$
with $s, t$ integral. Let $g : U' \to U$ be an integral morphism
such that every $R$-orbit in $U$ meets $g(U')$. Let $(U', R', s', t', c')$
be the restriction of $R$ to $U'$. If $u' \in U'$ is contained in an
$R'$-invariant affine open, then the image $u \in U$ is contained
in an $R$-invariant affine open of $U$.
\end{lemma}

\begin{proof}
Let $W' \subset U'$ be an $R'$-invariant affine open.
Set $\tilde R = U' \times_{g, U, t} R$ with maps
$\text{pr}_0 : \tilde R \to U'$ and $h = s \circ \text{pr}_1 : \tilde R \to U$.
Observe that $\text{pr}_0$ and $h$ are integral.
It follows that $\tilde W = \text{pr}_0^{-1}(W')$ is affine.
Since $W'$ is $R'$-invariant, the image
$W = h(\tilde W)$ is set theoretically $R$-invariant and
$\tilde W = h^{-1}(W)$ set theoretically (details omitted).
Thus, if we can show that $W$ is open, then $W$ is a scheme
and the morphism $\tilde W \to W$ is integral surjective
which implies that $W$ is affine by
Limits, Proposition \ref{limits-proposition-affine}.
However, our assumption on orbits meeting $U'$ implies
that $h : \tilde R \to U$ is surjective. Since an
integral surjective morphism is submersive
(Topology, Lemma \ref{topology-lemma-closed-morphism-quotient-topology}
and Morphisms, Lemma \ref{morphisms-lemma-integral-universally-closed})
it follows that $W$ is open.
\end{proof}

\noindent
The following technical lemma produces almost'' invariant
functions in the situation of a finite groupoid on a quasi-affine
scheme.

\begin{lemma}
\label{lemma-find-almost-invariant-function}
Let $(U, R, s, t, c)$ be a groupoid scheme with $s, t$ finite and of
finite presentation. Let $u_1, \ldots, u_m \in U$ be points whose $R$-orbits
consist of generic points of irreducible components of $U$.
Let $j : U \to \Spec(A)$ be an immersion.
Let $I \subset A$ be an ideal such that $j(U) \cap V(I) = \emptyset$
and $V(I) \cup j(U)$ is closed in $\Spec(A)$.
Then there exists an $h \in I$ such that $j^{-1}D(h)$
is an $R$-invariant affine open subscheme of $U$ containing
$u_1, \ldots, u_m$.
\end{lemma}

\begin{proof}
Let $u_1, \ldots, u_m \in V' \subset V \subset U$ be as in
Lemma \ref{lemma-invariant-affine-open-around-generic-point}.
Since $U \setminus V$ is closed in $U$, $j$ an immersion, and $V(I) \cup j(U)$
is closed in $\Spec(A)$, we can find an ideal
$J \subset I$ such that $V(J) = V(I) \cup j(U \setminus V)$.
For example we can take the ideal of elements of $I$ which
vanish on $j(U \setminus V)$. Thus we can replace
$(U, R, s, t, c)$, $j : U \to \Spec(A)$, and $I$ by
$(V', R', s', t', c')$, $j|_{V'} : V' \to \Spec(A)$, and $J$.
In other words, we may assume that $U$ is affine and that
$s$ and $t$ are finite locally free.
Take any $f \in I$ which does not vanish at all the
points in the $R$-orbits of $u_1, \ldots, u_m$
(Algebra, Lemma \ref{algebra-lemma-silly}). Consider
$$g = \text{Norm}_s(t^\sharp(j^\sharp(f))) \in \Gamma(U, \mathcal{O}_U)$$
Since $f \in I$ and since $V(I) \cup j(U)$ is closed we see that
$U \cap D(f) \to D(f)$ is a closed immersion. Hence $f^ng$ is the
image of an element $h \in I$ for some $n > 0$. We claim that $h$ works.
Namely, we have seen in
Groupoids, Lemma \ref{groupoids-lemma-determinant-trick}
that $g$ is an $R$-invariant function, hence $D(g) \subset U$
is $R$-invariant. Since $f$ does not vanish on the orbit of $u_j$,
the function $g$ does not vanish at $u_j$. Moreover, we have
$V(g) \supset V(j^\sharp(f))$ and hence $j^{-1}D(h) = D(g)$.
\end{proof}

\begin{lemma}
\label{lemma-no-specializations-map-to-same-point}
Let $(U, R, s, t, c)$ be a groupoid scheme. If $s, t$ are finite,
and $u, u' \in R$ are distinct points in the same orbit,
then $u'$ is not a specialization of $u$.
\end{lemma}

\begin{proof}
Let $r \in R$ with $s(r) = u$ and $t(r) = u'$. If $u \leadsto u'$
then we can find a nontrivial specialization $r \leadsto r'$ with
$s(r') = u'$, see
Schemes, Lemma \ref{schemes-lemma-quasi-compact-closed}.
Set $u'' = t(r')$. Note that $u'' \not = u'$ as there are no
specializations in the fibres of a finite morphism.
Hence we can continue and find a nontrivial specialization
$r' \leadsto r''$ with $s(r'') = u''$, etc. This shows that the
orbit of $u$ contains an infinite sequence
$u \leadsto u' \leadsto u'' \leadsto \ldots$
of specializations which is nonsense as the orbit
$t(s^{-1}(\{u\}))$ is finite.
\end{proof}

\begin{lemma}
\label{lemma-get-affine}
Let $j : V \to \Spec(A)$ be a quasi-compact immersion of schemes.
Let $f \in A$ be such that $j^{-1}D(f)$ is affine and $j(V) \cap V(f)$
is closed. Then $V$ is affine.
\end{lemma}

\begin{proof}
This follows from Morphisms, Lemma \ref{morphisms-lemma-get-affine}
but we will also give a direct proof.
Let $A' = \Gamma(V, \mathcal{O}_V)$. Then $j' : V \to \Spec(A')$ is a
quasi-compact open immersion, see
Properties, Lemma \ref{properties-lemma-quasi-affine}.
Let $f' \in A'$ be the image of $f$. Then $(j')^{-1}D(f') = j^{-1}D(f)$
is affine. On the other hand, $j'(V) \cap V(f')$ is a subscheme of
$\Spec(A')$ which maps isomorphically to the closed subscheme
$j(V) \cap V(f)$ of $\Spec(A)$. Hence it is closed in $\Spec(A')$
for example by Schemes, Lemma \ref{schemes-lemma-section-immersion}.
Thus we may replace $A$ by $A'$ and assume that $j$ is an open immersion
and $A = \Gamma(V, \mathcal{O}_V)$.

\medskip\noindent
In this case we claim that $j(V) = \Spec(A)$ which finishes the proof.
If not, then we can find a principal affine open $D(g) \subset \Spec(A)$
which meets the complement and avoids the closed subset $j(V) \cap V(f)$.
Note that $j$ maps $j^{-1}D(f)$ isomorphically onto $D(f)$, see
Properties, Lemma \ref{properties-lemma-invert-f-affine}.
Hence $D(g)$ meets $V(f)$. On the other hand, $j^{-1}D(g)$
is a principal open of the affine open $j^{-1}D(f)$ hence affine.
Hence by
Properties, Lemma \ref{properties-lemma-invert-f-affine}
again we see that $D(g)$ is isomorphic to $j^{-1}D(g) \subset j^{-1}D(f)$
which implies that $D(g) \subset D(f)$. This contradiction finishes
the proof.
\end{proof}

\begin{lemma}
\label{lemma-find-affine-codimension-1}
Let $(U, R, s, t, c)$ be a groupoid scheme. Let $u \in U$. Assume
\begin{enumerate}
\item $s, t$ are finite morphisms,
\item $U$ is separated and locally Noetherian,
\item $\dim(\mathcal{O}_{U, u'}) \leq 1$ for every point $u'$
in the orbit of $u$.
\end{enumerate}
Then $u$ is contained in an $R$-invariant affine open of $U$.
\end{lemma}

\begin{proof}
The $R$-orbit of $u$ is finite. By conditions (2) and (3) it is contained
in an affine open $U'$ of $U$, see
Varieties, Proposition
\ref{varieties-proposition-finite-set-of-points-of-codim-1-in-affine}.
Then $t(s^{-1}(U \setminus U'))$ is an $R$-invariant
closed subset of $U$ which does not contain $u$. Thus
$U \setminus t(s^{-1}(U \setminus U'))$ is an $R$-invariant open
of $U'$ containing $u$.
Replacing $U$ by this open we may assume $U$ is quasi-affine.

\medskip\noindent
By Lemma \ref{lemma-find-affine-integral} we may replace $U$ by its reduction
and assume $U$ is reduced. This means $R$-invariant subschemes
$W' \subset W \subset U$ of
Lemma \ref{lemma-finite-flat-over-almost-dense-subscheme}
are equal $W' = W$. As $U = t(s^{-1}(\overline{W}))$ some point
$u'$ of the $R$-orbit of $u$ is contained in $\overline{W}$
and by Lemma \ref{lemma-find-affine-integral}
we may replace $U$ by $\overline{W}$ and $u$ by $u'$.
Hence we may assume there is
a dense open $R$-invariant subscheme $W \subset U$ such that
the morphisms $s_W, t_W$ of the restriction $(W, R_W, s_W, t_W, c_W)$ are
finite locally free.

\medskip\noindent
If $u \in W$ then we are done by
Groupoids, Lemma \ref{groupoids-lemma-find-invariant-affine}
(because $W$ is quasi-affine so any finite set of points
of $W$ is contained in an affine open, see
Properties, Lemma \ref{properties-lemma-ample-finite-set-in-affine}).
Thus we assume $u \not \in W$ and hence none of the points of the
orbit of $u$ is in $W$. Let $\xi \in U$
be a point with a nontrivial specialization to a point $u'$ in the orbit
of $u$. Since there are no specializations among the points in the
orbit of $u$ (Lemma \ref{lemma-no-specializations-map-to-same-point})
we see that $\xi$ is not in the orbit.
By assumption (3) we see that $\xi$ is a generic point of $U$
and hence $\xi \in W$.
As $U$ is Noetherian there are finitely many of these
points $\xi_1, \ldots, \xi_m \in W$. Because $s_W, t_W$ are flat the orbit
of each $\xi_j$ consists of generic points of irreducible components
of $W$ (and hence $U$).

\medskip\noindent
Let $j : U \to \Spec(A)$ be an immersion of $U$ into an affine scheme
(this is possible as $U$ is quasi-affine). Let $J \subset A$
be an ideal such that $V(J) \cap j(W) = \emptyset$ and $V(J) \cup j(W)$
is closed. Apply Lemma \ref{lemma-find-almost-invariant-function}
to the groupoid scheme $(W, R_W, s_W, t_W, c_W)$, the morphism
$j|_W : W \to \Spec(A)$, the points $\xi_j$, and the ideal $J$
to find an $f \in J$ such that $(j|_W)^{-1}D(f)$ is an $R_W$-invariant
affine open containing $\xi_j$ for all $j$. Since $f \in J$
we see that $j^{-1}D(f) \subset W$, i.e., $j^{-1}D(f)$ is
an $R$-invariant affine open of $U$ contained in $W$
containing all $\xi_j$.

\medskip\noindent
Let $Z$ be the reduced induced closed subscheme structure on
$$U \setminus j^{-1}D(f) = j^{-1}V(f).$$
Then $Z$ is set theoretically
$R$-invariant (but it may not be scheme theoretically $R$-invariant).
Let $(Z, R_Z, s_Z, t_Z, c_Z)$ be the restriction of $R$ to $Z$.
Since $Z \to U$ is finite, it follows that $s_Z$ and $t_Z$ are finite.
Since $u \in Z$ the orbit of $u$ is in $Z$ and agrees with the
$R_Z$-orbit of $u$ viewed as a point of $Z$. Since
$\dim(\mathcal{O}_{U, u'}) \leq 1$ and since $\xi_j \not \in Z$
for all $j$, we see that $\dim(\mathcal{O}_{Z, u'}) \leq 0$ for
all $u'$ in the orbit of $u$. In other words, the $R_Z$-orbit of $u$
consists of generic points of irreducible components of $Z$.

\medskip\noindent
Let $I \subset A$ be an ideal such that $V(I) \cap j(U) =\emptyset$
and $V(I) \cup j(U)$ is closed. Apply
Lemma \ref{lemma-find-almost-invariant-function} to
the groupoid scheme $(Z, R_Z, s_Z, t_Z, c_Z)$, the restriction $j|_Z$,
the ideal $I$, and the point $u \in Z$ to obtain $h \in I$ such that
$j^{-1}D(h) \cap Z$ is an $R_Z$-invariant open affine containing $u$.

\medskip\noindent
Consider the $R_W$-invariant (Groupoids, Lemma
\ref{groupoids-lemma-determinant-trick}) function
$$g = \text{Norm}_{s_W}(t_W^\sharp(j^\sharp(h)|_W)) \in \Gamma(W, \mathcal{O}_W)$$
(In the following we only need the restriction of $g$ to $j^{-1}D(f)$ and
in this case the norm is along a finite locally free morphism of affines.)
We claim that
$$V = (W_g \cap j^{-1}D(f)) \cup (j^{-1}D(h) \cap Z)$$
is an $R$-invariant affine open of $U$ which finishes the proof of the lemma.
It is set theoretically $R$-invariant by construction. As $V$ is a
constuctible set, to see that it is open it suffices to show it is
closed under generalization in $U$ (Topology, Lemma
\ref{topology-lemma-characterize-closed-Noetherian}
or the more general
Topology, Lemma
\ref{topology-lemma-constructible-stable-specialization-closed}).
Since $W_g \cap j^{-1}D(f)$ is open in $U$, it suffices to consider
a specialization $u_1 \leadsto u_2$ of $U$ with
$u_2 \in j^{-1}D(h) \cap Z$.
This means that $h$ is nonzero in $j(u_2)$ and $u_2 \in Z$.
If $u_1 \in Z$, then $j(u_1) \leadsto j(u_2)$ and since
$h$ is nonzero in $j(u_2)$ it is nonzero in $j(u_1)$ which
implies $u_1 \in V$. If $u_1 \not \in Z$ and
also not in $W_g \cap j^{-1}D(f)$, then $u_1 \in W$, $u_1 \not \in W_g$
because the complement of $Z = j^{-1}V(f)$ is contained in $W \cap j^{-1}D(f)$.
Hence there exists a point $r_1 \in R$ with $s(r_1) = u_1$
such that $h$ is zero in $t(r_1)$. Since $s$ is finite we
can find a specialization $r_1 \leadsto r_2$ with $s(r_2) = u_2$.
However, then we conclude that $f$ is zero in $u'_2 = t(r_2)$
which contradicts the fact that $j^{-1}D(h) \cap Z$
is $R$-invariant and $u_2$ is in it. Thus $V$ is open.

\medskip\noindent
Observe that $V \subset j^{-1}D(h)$ for our function $h \in I$.
Thus we obtain an immersion
$$j' : V \longrightarrow \Spec(A_h)$$
Let $f' \in A_h$ be the image of $f$. Then $(j')^{-1}D(f')$
is the principal open determined by $g$ in the affine
open $j^{-1}D(f)$ of $U$.
Hence $(j')^{-1}D(f)$ is affine. Finally,
$j'(V) \cap V(f') = j'(j^{-1}D(h) \cap Z)$
is closed in $\Spec(A_h/(f')) = \Spec((A/f)_h) = D(h) \cap V(f)$
by our choice of $h \in I$ and the ideal $I$. Hence we can apply
Lemma \ref{lemma-get-affine}
to conclude that $V$ is affine as claimed above.
\end{proof}

There are no comments yet for this tag.

## Add a comment on tag 0AB8

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the lower-right corner).


text:
## 8.3 Variables

A variable is an expression. If a variable is bound to a value, the return value is this value. Unbound variables are only allowed in patterns.

Variables start with an uppercase letter or underscore (_). Variables can contain alphanumeric characters, underscore and @.

Examples:

XName1PhoneNumberPhone_number__Height

Variables are bound to values using pattern matching. Erlang uses single assignment, that is, a variable can only be bound once.

The anonymous variable is denoted by underscore (_) and can be used when a variable is required but its value can be ignored.

Example:

[H|_] = [1,2,3]

Variables starting with underscore (_), for example, _Height, are normal variables, not anonymous. They are however ignored by the compiler in the sense that they do not generate any warnings for unused variables.

Example:

The following code:

member(_, []) ->    [].

can be rewritten to be more readable:

member(Elem, []) ->    [].

This causes a warning for an unused variable, Elem, if the code is compiled with the flag warn_unused_vars set. Instead, the code can be rewritten to:

member(_Elem, []) ->    [].

Notice that since variables starting with an underscore are not anonymous, this matches:

{_,_} = {1,2}

But this fails:

{_N,_N} = {1,2}

The scope for a variable is its function clause. Variables bound in a branch of an if, case, or receive expression must be bound in all branches to have a value outside the expression. Otherwise they are regarded as 'unsafe' outside the expression.

For the try expression variable scoping is limited so that variables bound in the expression are always 'unsafe' outside the expression.


text:
# My Oreo manifesto

Math is powerful.

No one has demonstrated this more frequently and more convincingly than Al Sicherman of the StarTribune. In his Tidbits column, Sicherman keeps tabs on prices and variations of processed foods. A favorite category for him recently has been Oreos. Writing recently on the topic of the new Peppermint Creme Oreos (which he describes as toothpastey), Sicherman says:

All of that is not to say that there is no significant difference between Cool Mint Creme Oreos and Peppermint Creme Oreos: They are the same price on the shelf, but the package of Cool mint Oreos is 15.25 ounces (30 cookies), and that of Peppermint Creme Oreos is 10.5 ounces (20 cookies). So Peppermint Creme Oreos cost 45 percent more per ounce — or 50 percent more per cookie.

Whoomp! There it is! Math, baby!

Gotta love this guy. (But seriously, would it kill the Strib to dispatch a photographer with a camera that has more than 1 megapixel?)

Inspired by his example, I’m prepared to turn up the heat on Nabisco’s Oreo division. Are you ready?

Double Stuf isn’t double stuf.

Let me say that again…DOUBLE STUF IS NOT DOUBLE STUF!

How do I know? Math.

How should we do this? Reductio ad absurdum? Let’s assume it is double stuf. Then, according to Nabisco’s own data (found on the Nutrition Facts), one serving of Oreos is 3 cookies and 160 calories. Double Stuf is 2 cookies and 140 calories.

Let me translate that for you. One serving of regular Oreos has 6 wafers, 3 stufs and 160 calories. Meanwhile one serving of Double Stuf Oreos has 4 wafers, 4 stufs and 140 calories.

That’s hard to compare. So let’s consider two servings of regular Oreos (6 cookies, 12 wafers, 6 stufs, 320 calories) and three servings of Double Stuf (6 cookies, 12 wafers, 12 stufs and 420 calories).

Those Double Stuf Oreos account for 6 additional stufs and 100 additional calories (same number of wafers, remember). We conclude that each stuf is approx. 17 calories. And from this we can conclude that each wafer has approx. 19 calories.

What, you prefer the formal mathematical solution? Fair enough:

Let w be the number calories in a wafer and f be the number of calories in a unit of stuf. Then Nabisco’s calorie claims yield this system of equations:

$\begin{cases} 6w+3f=160 \\ 4w+4f=140 \end{cases}$

We can rewrite this equivalently as:

$\begin{cases} 12w+6f=320 \\ 12w+12f=420 \end{cases}$

And then solving by combination, we get:

$6f=100$ or $f=16 \frac{2}{3}$

You’re comfortable with that. No problem, right?

Tune in tomorrow for the dénouement.

### 13 responses to “My Oreo manifesto”

1. Nice!!! I think I may spin this idea for my AP Statistics class but will absolutely use it in my Algebra 2 class. Thanks!!!

2. I am so excited about this! I am teaching systems in Algebra next week. I have to ask if it is against our Health and Wellness Policy to bring in Oreos (they are ok for peanut allergies, right?)

How old is Al Sicherman? It seems like he’s been around forever.

3. Christopher

Anna, I don’t know Al’s age. I’m guessing not a day older than 39! I’m hoping he’ll stop by; couldn’t find his email address through the STrib website, so I tweeted the address for the Taste section to invite him for a read.

I’ve got another junk food based system of equations application up my sleeve. I probably won’t get to it before next week, though. Stay tuned.

4. Ooh! We have a wonderful cookie in Australia called the Tim Tam (you haven’t lived if you haven’t had a packet – Aussies ship them to friends in US in ‘care packages’) who also do a ‘double choc’ version. Will have to try this in my algebra classes this year! Thanks for the idea.

• Christopher

Mmmm…Can’t wait to try a Tim Tam.

5. Al Sicherman

AARGH: Here’s the whole thing:

Hi, Christopher:

First, thanks for the very kind words. The new-groceries beat is full of examples of one kind of stupidity or another, but the Oreo is the easiest and silliest target I have been lucky enough to glom onto.

More than a year ago I started to take on the matter of how much of what (cookie/filling) were provided in the various versions of Oreos then available (original, double stuf, chocolate, double chocolate stuf, mint, etc.). But it was going to get rather intensely numerical, and my editor believes (correctly, I’m afraid) that most readers drop out by the second appearance of a calculation — which is when I’m just warming up. (I used to be an electrical engineer.)

I wasn’t aware of your blog until you let the Taste section folks know about it, and I admire your willingness to stand up and be seen with a figurative slide rule in your hand.

All that said, I’m afraid I have to disagree with your conclusion about the Double Stuf Oreo. As you noted, having reached a contradiction means that something in your original formulations was wrong, but it wasn’t necessarily your assumption that double stuf is truly double. You also assumed that the chocolate and vanilla stufs in the Triple Double are the same, which they probably aren’t (two Chocolate Double Stuf Oreos are 150 calories, not the 140 of the vanilla Double Stuf). It could also be the assumption that the wafers are all the same (they may not be; see below). Or it could be any two or all three of those assumptions. Or something else neither of us has thought of; the world is unfortunately full of unrecognized assumptions.

About the wafers: A comparatively simple exercise (less simple but far more stupid exercises follow) demonstrates that, at least, they are different in diameter: Attached photo No. 1 shows a row of 10 original Oreos and one of 10 Double Stuf Oreos edge-to-edge. The top row (the Doubles) is a good 1/2 inch longer than the row of original Oreos. Another measure — stacking a whole bunch of wafers devoid of their glop — appears to indicate that all are the same thickness -– eight of either kind measure about 1 1/2 inches, for a thickness of 3/16 inch per wafer. But nothing says that they are the same density. And in fact, the closeup shot, not flash-lit (photo No. 2), reveals that the Double Stuf cookies are slightly lighter in color, a possible indicator of less density from more air –- or maybe from less cocoa.

So I took apart and weighed a whole bunch of original and Double Stuf Oreos and their components. (There is almost no depth to which I will not descend in pursuit of my art.)

This is where, in a perfect world, I (or my dashing — and much younger — alter ego, Mr. Tidbit) would provide a collection of stunningly dramatic (or at least consistent) numbers: weights of wafers, single fillings and double fillings. Unfortunately, even weighing a bunch of each item together failed to overcome many problems: the amount of filling I left behind on scraped-off wafers, the amount of wafer crumbs that got weighed with the filling, the horrible performance of my cheap digital scale (which repeatedly produced different readings when reweighing the same stuff), and the distinct, but untested, possibility that (gasp!) there might be some variability between batches of Oreos.

As close as I came, anyway, surrounded by the litter of broken Oreo wafers and little piles of Oreo glop (see photo No. 3), was to conclude that it is quite possible that Double Stuf Oreos indeed contain twice the stuf.

My best evidence of that follows not from all that pointless weighing but from noting that a stack of nine Double Stufs is approximately the same height as 11 originals: about 5 3/16 inches.

(I found it impossible to measure the height of stuf directly, partly because it often varies considerably across the width of the cookie, and partly because my every attempt to separate a number of stufs intact from cookies, in order to stack up such a number of stufs, was a total failure.)

The following discussion ignores the possibility that the diameters of the double filing and the original filling might be different, so even if the height of a Double Stuf filling is twice that of an original filling there might be a difference in the total amount of glop involved. I ignored that possibility because I didn’t think of it until just now –- and it’s too late to measure because, to the dismay of my dog, I have pitched all the bits of cookie and filling, and one package of each kind of cookie is as much as I care to invest in this enterprise.

Anyway:

11 originals = 9 Double Stufs = 5 3/16 inches
or
22w + 11f = 18w + 9d = 5 3/16

where w is the height of a single wafer of either sort (3/16 inch, as noted above), f is the height of the filling of an original Oreo and d is the height of a Double Stuf filling

For the originals,

22w + 11f = 5 3/16
22 * 3/16 + 11f = 83/16
66/16 + 11f = 83/16
11f = 17/16
f = 17/176 — approximately 0.10 inches

And for the Double Stufs:

18w + 9d = 5 3/16
18 * 3/16 + 9d = 83/16
54/16 + 9d = 83/16
9d = 29/16
d = 29/144 — approximately 0.20 inches

Cheers,

Al Sicherman
0.20 inchesichermanA


text:
# What would be the best way to design a real time clock for the MSP430?

Basically that. The way I am doing it now is with the TimerA set to 1 second interrupts. But I think that it's very annoying. Are there any other ways to do it?

I want to basically set timers on that clock, like, shutdown until 40 seconds have passed...

• What is annoying about it? – markrages Aug 5 '11 at 21:17

## 3 Answers

It's not perfectly clear to whether you want a real-time clock or a stopwatch (the 40 seconds you mention).

You could use an RTC IC (Real-Time Clock), like the NXP PCF8563. This one is available in several packages, including both the old DIL and a very small DFN.
But you probably don't need a separate RTC IC. It's typically used because it consumes very little power, and the rest of the circuit can power down while the RTC keeps running of a battery or supercap. The MSP430, however, is also a low-power device, and it has a low-frequency oscillator which can run on the same 32.768kHz crystal you would use for the RTC.
In one project I had the MSP430 running continuously on a 32kHz crystal, and yet it consumed less than 5$\mu$A. That's more than an RTC (the PCF8563 only needs 250nA), but it will be acceptable for many applications.

What's your problem with the 1s interrupt? If you want to make a real-time clock you'll need a time-cue anyhow, whether generated internally or coming from an external RTC. Upon interrupt you can perform required updates of seconds, minutes and hour counters, and wait for the next interrupt. You even could work with 10ths of a second, although with the 32.768kHz this will have a minor deviation. You would have four tenths of a second or 3277 clock ticks, followed by one tenth of 3278 ticks, to get exactly 1/2 second, so repeat this pattern a second time to complete one second.

There are MSP430 devices with a low-power oscillator that use a standard 32.768 kHz watch crystal and are intended specifically for that sort of application. A typical one is the MSP430F1101.

• Timer A and the watch crystal is the best way for the msp430 to keep time – jsolarski Aug 5 '11 at 22:21

Usually a real-time clock is done by either having a real-time clock module built in to the microcontroller, or to use an external real-time clock module such as the DS1305 from Maxim.

These can typically be programmed to trigger an interrupt at a pre-defined time, and run off their own 32.768KHz crystal. They often have their own battery-backup circuit, and some even contain charge circuits too.

• That would be great, but I have an already developed platform, mainly a zolertia z1, which does not have any kind of realtime module. I can only rely on the microcontrollers clocks... – Sergio Campamá Aug 5 '11 at 20:39


text:
# What is condition for second degree equation to represent a pair of straight lines?

According to my text the necessary and sufficient condition for a general equation of second degree i.e. $ax^2 + 2hxy + by^2 + 2gx + 2fy + c = 0$ to represent a pair of straight lines is that 1) the discriminant $abc + 2fgh - af^2 - bg^2 - cf^2 = 0$ and 2) $h^2 \ge ab, g^2 \ge ca$ and $f^2 \ge bc$. I was able to prove part 1) but I am not able to work out why part 2) should always be satisfied. Can someone help prove part 2) and what happens if part 1) is true but part 2) is false?

I think $h^2 \ge ab$ must always be true because then angle between two lines represented by the equation of second degree will be not defined as $tan \theta = {2 \sqrt{h^2-ab} \over a+b}$ where $\theta$ is angle between two lines.

• With $h^2<ab$, the trinomial formed by the quadratic terms is positive (or negative) definite, hence the conic is of the ellipse type. – Yves Daoust Apr 14 '16 at 20:38

If the conic represents a pair of lines, then it can be written as $(px+qy+r)(p'x+q'y+r')$. Therefore, we get $ab = pp'qq'$ and $h = \frac{pq'+p'q}{2}$.

1) If both $pq'$ and $p'q$ are greater than equal to zero then apply AM-GM to $pq'$ and $p'q$ to get

$$\frac{pq'+ p'q}{2} \geq \sqrt{pq' \cdot p'q}$$

Squaring both sides, we get

$$h^2 = {\bigg(\frac{pq'+ p'q}{2}\bigg)}^2 \geq pp'qq' = ab$$

2) If exactly one of $pq'$ and $p'q$ is less than zero then $ab \leq 0$ and therefore is always less than equal to $h^2 \geq 0$.

3) If both $pq'$ and $p'q$ are less than zero then apply AM-GM to $-pq'$ and $-p'q$ to get

$$\frac{-pq'+ (-p'q)}{2} \geq \sqrt{-pq' \cdot -p'q} = \sqrt{pp'qq'}$$

Squaring both sides, we get

$$h^2 = {\bigg(\frac{-pq'+ (-p'q)}{2}\bigg)}^2 \geq pp'qq' = ab$$

The other two conditions come out in a similar manner.

• thanks that was pretty easy.! – Matt Apr 14 '16 at 21:04
• I realized that we can't quite apply AM-GM since $a$ and $b$ need not be positive in general. But in that case, $ab \leq 0$ and is hence less than equal to the square $h^2$. – Seven Apr 14 '16 at 21:11
• may you please show how can we prove any one of three by A.M G.M inequality? – Matt Apr 15 '16 at 17:11
• @Raghav I have elaborated on the answer. Hope that helps. – Seven Apr 15 '16 at 20:36

Hint:

The classification of conics is done through the quadratic form in $\mathbf R^3$ associated to the matrix $$\begin{pmatrix} a&h&g\\h&b&f\\g&f&c \end{pmatrix}.$$ The conic splits into two lines if and only if the quadratic form has signature $(1,1)$.


text:
# Proving all rational numbers including negatives are countable

In this proof can I show independently that positive rationals and negative rationals are countable by using Cantor's zigzag and then say that the union of two countable sets is countable so therefore

positive and negative rationals are countable.

Is this correct ?

-
irrationals are countable? when did this happen. –  simplicity Feb 10 '12 at 2:42
- ( 1/3) , -(1/4) , -(3/7) = negative rational numbers –  user602774 Feb 10 '12 at 2:45
The confusion arose as a result of a bad edit. I don't believe OP ever intended to claim the irrationals are countable.//To OP: What you say about the union of two countable sets is absolutely correct. The set of all rational numbers (positive or negative) is indeed countable. –  Austin Mohr Feb 10 '12 at 2:46
Sorry guys my bad. The OP spelt rationals as "rrationals" so subconsciously in my mind the edit was to put an "i" there. –  user38268 Feb 10 '12 at 2:54

$\\ \frac{1}{1}, -\frac{1}{1}, \frac{1}{2}, -\frac{1}{2}, \ldots \\ \frac{2}{1}, -\frac{2}{1}, \frac{2}{2}, -\frac{2}{2}, \ldots \\ \vdots \\ \frac{n}{1}, -\frac{n}{1}, \frac{n}{2}, -\frac{n}{2}, \ldots \\ \vdots$
or use your favourite matrix (this one is missing $0$, by the way).


text:
# Article

 Title: The determination of factors in linear models of factor analysis (English) Author: Kratochvíl, Petr Language: English Journal: Aplikace matematiky ISSN: 0373-6725 Volume: 35 Issue: 5 Year: 1990 Pages: 350-355 Summary lang: English . Category: math . Summary: The author shows that a decomposition of a covariance matrix $\bold{\sum = AA'}$ implies the corresponding model, i.e. the existence of factors $f_j$ such that $\sum a_{ij}f_j$ is true. The result is applied to the general linear model of factor analysis. A procedure for computing the factor score is proposed. (English) Keyword: factor score Keyword: linear model Keyword: existence of factors Keyword: singular value decomposition Keyword: decomposition of a covariance matrix MSC: 62H05 MSC: 62H25 idZBL: Zbl 0721.62060 idMR: MR1072605 . Date available: 2008-05-20T18:39:44Z Last updated: 2015-05-31 Stable URL: http://hdl.handle.net/10338.dmlcz/104416 . Reference: [1] T. W. Anderson: An Introduction to Multivariate Statistical Analysis.Second Edition, John Wiley & sons, 1984. Zbl 0651.62041, MR 0771294 Reference: [2] T. W Anderson, Herman Rubin: Statistical inference in factor analysis.Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability (Jerzy Neyman, ed.), Vol. V, University of California, Berkeley and Los Angeles, 1956. MR 0084943 Reference: [3] P. Blahuš: Factor analysis and its generalization.Matematický seminář SNTL, sv. 21, Praha 1985 (in Czech, russian translation to appear). Reference: [4] P. Kratochvíl J. Nekola: Modelling of the research activity with the use of factor analysis.(Czech). Ekonomicko-matematický obzor 15 (1979), 295-309. .

## Files

Files Size Format View
AplMat_35-1990-5_2.pdf 824.0Kb application/pdf View/Open

Partner of


text:
Journal article

### Search for pair-produced heavy quarks decaying to Wq in the two-lepton channel at root(s)=7 TeV with the ATLAS detector

Abstract:

A search is presented for heavy-quark pair production (QQ̄) under the decay hypothesis QQ̄→W+qW-q̄ with q=d, s, b for up-type Q or q=u, c for down-type Q. The search is performed with 1.04fb-1 of integrated luminosity from pp collisions at √s=7TeV collected by the ATLAS detector at the CERN LHC. Dilepton final states are selected, requiring large missing transverse momentum and at least two jets. Mass reconstruction of heavy-quark candidates is performed by assuming that the W boson decay pro...

Publication status:
Published

### Access Document

Publisher copy:
10.1103/PhysRevD.86.012007

### Authors

Abdallah, J More by this author
Abdelalim, AA More by this author
Abdesselam, A More by this author