How to express a conditional in a summation

Question

I have a question about notation: What's the proper mathematical notation to write (sum from i=1 to X)(sum from j=1 to X) 1 if gcd(i,j)==2, 0 otherwise?

Do you mean that you want to include only those pairs of indices $i,j$ for which $\gcd(i,j)=2$? Or might you have meant $\gcd(i,j)\ne2$? — Michael Hardy, Mar 08 '13 at 00:49

score 1 · Accepted Answer · answered Mar 08 '13 at 00:49

1

For that Knuth uses Iverson's convention: $[\gcd(i, j) = 2]$ is 1 if the condition is true, 0 if false.

answered Mar 08 '13 at 00:49

vonbrand

27,812

[gcd(i,j)=2] by itself means 1 if true, 0 if false? – Sean Hill Mar 08 '13 at 00:50
Yes, BUT if you are going to use this notation I would advise letting everybody know as not everyone will understand otherwise. – Gerry Myerson Mar 08 '13 at 00:57

score 1 · Answer 2 · edited Mar 08 '13 at 00:52

1

There is the Kronecker delta $\delta_{i,j}=0$ if $i\neq j$ 1 otherwise.

For you $\sum_{i=1}^X \sum_{j=1}^X \delta_{\gcd(i,j),2}$.

I hope it helps.

edited Mar 08 '13 at 00:52

Michael Hardy

1

answered Mar 08 '13 at 00:51

wece

2,732

score 1 · Answer 3 · answered Mar 08 '13 at 01:11

I might just write $$ \sum_{\begin{smallmatrix} 1\le i\le X \\ 1\le j\le X \\ \gcd(i,j)=2 \end{smallmatrix}} 1. $$

If you need to write it as an iterated sum, you could write $$ \sum_{1\le i\le X} \sum_{\begin{smallmatrix} 1\le j \le X \\ \gcd(i,j)=2 \end{smallmatrix}} 1. $$

But it won't do to write $$ \sum_{\begin{smallmatrix} 1\le i \le X \\ \gcd(i,j)=2 \end{smallmatrix}} \sum_{1\le j \le X } 1 $$ because there's not yet anything called $j$. For example, suppose one has $$ \sum_{i=1}^4 \sum_{j=1}^3 (i^2+j). $$ This is $$ \underbrace{\Big((1^2+1)+(1^2+2)+(1^2+3)\Big)}_{i=1} + \underbrace{\Big((2^2+1)+(2^2+2)+(2^2+3)\Big)}_{i=2} + \underbrace{\Big((3^2+1)+(3^2+2)+(3^2+3)\Big)}_{i=3} $$

Within the term in which $i=2$, we find one term in which $j=2$ and two other terms. But we cannot include or exclude in its entirety the term labeled with the $\underbrace{\text{underbrace}}$ as $i=2$ on the grounds of its relationship with some other variable called $j$.

Gerry Myerson · Answer 4 · 2013-03-08T01:01:11.233

0

$$\sum_{1\le i\le X,\gcd(i,j)=2}\sum_{1\le j\le X}1$$ will do. Also, you could look up the Iverson bracket notation.

EDIT: Sorry, make that $$\sum_{1\le i\le X}\sum_{1\le j\le X,\gcd(i,j)=2}1$$ (Thanks, Michael)

edited Mar 08 '13 at 01:01

answered Mar 08 '13 at 00:48

Gerry Myerson

179,216

I don't see how this can work. You're writing $\displaystyle\sum_{1\le i\le X,\ \gcd(i,j)=1}\left(\sum_{1\le j\le X}\cdots\cdots\cdots\right)$. You're referring to the index $j$ in the outside summation, although $j$ is a variable bound by the inside summation. – Michael Hardy Mar 08 '13 at 00:52

Julien · Answer 5 · 2013-03-08T01:13:38.643

0

You could do something like this, for instance: $$ f(X)=\sum_{1\leq i,j\leq X, (i,j)=2}^X1=1+2\sum_{1\leq i<j\leq X, (i,j)=2}^X1 $$ $$ =1+2\sum_{2\leq 2i<2j\leq X, (i,j)=1}^X1 $$ $$ =1+2\sum_{j=1}^{\lfloor X/2\rfloor}\sum_{1\leq i<j, (i,j)=1}1 $$ $$ =1+2\sum_{j=2}^{\lfloor X/2\rfloor}\phi(j) $$ where $\phi(j)$ is Euler's totient function which counts the number of $i$ between $1$ and $j$ such that $(i,j)=1$.

This way you can get an asymptotic estimate: $$ f(X)=\frac{3X^2}{4\pi^2}+O(X\log X). $$

edited Mar 08 '13 at 01:13

answered Mar 08 '13 at 01:07

Julien

44,791

@user64283 In case it is of any use, I developed the formula a little bit to express it with Euler's totient function and obtain an asymptotic estimate. – Julien Mar 08 '13 at 01:10

How to express a conditional in a summation

5 Answers5