text:
# Chapter 3: Atomic Packing¶

## Exa 3.1¶

In [1]:
from __future__ import division
import math
#  Python  Code  Ex3.1  Packing  of  equal  spheres  in
#two  dimensional  square  lattice:Page-88(2010)

#Variable declaration

a=1;         #  Length  of  the  side  of  the  square,  unit
R  =  a/2;                               #  Radius  of  the  sphere,  unit

#Calculations

# Radius of  the  sphere  introduced  within  the  void  produced  by
# the  packing  of  equal  spheres  on  square  lattice,  unit
r  =  ((2)**0.5-1)*R;
A  =  math.pi*R**2;      #  Area  associated  with  a  sphere,  square  units
FA  =  a**2-A;#Free area occupied  by  void  in  square  lattice,square  units
FA_per  =  FA*100;    #  Percentage  free  area  in  square  lattice

#Result

print"\nFree  area  in  square  lattice  is  :",round(FA_per,2),"percent"

Free  area  in  square  lattice  is  : 21.46 percent

## Exa 3.2¶

In [2]:
from __future__ import division
import math
# Python Code Ex3.2 Packing efficiency in diamond structure: Page-92 (2010)

#Variable declaration

# For simplicity we may take radius of the atom, R = 1 unit
R = 1;                           # Radius of the atom in bcc lattice, unit
nc = 8;                   # Number of corner atoms in diamond structure
nfcc = 6;                  # Number of face centred atoms in diamond structure
na = 4;                      # Number of atoms completely within the unit cell

#Calculations

n = 1/8*nc+1/2*nfcc+1*na  # Effective number of atoms in the diamond structure
V_atom = 8*4/3*math.pi*R**3; # Volume of atoms within the unit cell, unit cube
# Since for a diamond cubic crystal, the space lattice is fcc,
#with two atos per lattice point, such that 8*R = sqrt(3)*a, solving for a
a = 8*R/(3)**0.5;       # lattice parameter of diamond structure, unit
V_cell = a**3;                 # Volume of the unit cell, unit cube
eta = V_atom/V_cell*100;    # Packing efficiency in diamond structure

#Result

print"\nThe packing efficiency in diamond structure is :",round(eta),"percent"

The packing efficiency in diamond structure is : 34.0 percent

## Exa 3.3¶

In [3]:
from __future__ import division
import math
#  Python  Code  Ex3.3  Radius  of  largest  sphere
#that  can  be  placed  at  the  octahedral  void:  Page-100  (2010)

#Variable declaration

#  For  simplicity  we  may  take  radius  of  the  atom,  R  =  1  unit
R  =  1;                 #  Radius  of  the  atom  in  bcc  lattice,  unit

#Calculation

#  For  a  bcc  lattice,  4*R  =  a*sqrt(3),  solving  for  a
a  =  4*R/(3)**0.5;  #  lattice  parameter  of  bcc  crystal,  unit
#  Since  R  +  Rx  =  a/2,  solving  for  Rx
#Radius of  the largest sphere that will fit into the octahedral void, unit
Rx  =  a/2  -  R;

#Results

print"\nThe  radius  of  the  largest  sphere  that"
print " will  fit  into  the  octahedral  void  is  :",round(Rx,2),"R"

The  radius  of  the  largest  sphere  that
will  fit  into  the  octahedral  void  is  : 0.15 R

## Exa 3.4¶

In [4]:
from __future__ import division
import math
#  Python  Code  Ex3.4  Radius  of  largest  sphere  that
#can  be  placed  at  the  tetrahedral  void:  Page-100  (2010)

#Variable declaration

#  For  simplicity  we  may  take  radius  of  the  atom,  RL  =  1  unit
RL  =  1;       #  Radius  of  the  atom  in  bcc  lattice,  unit

#Calculation

#  For  a  bcc  lattice,  4*RL  =  a*sqrt(3),  solving  for  a
a  =  4*RL/(3)**0.5;    #  Lattice  parameter  of  bcc  crystal,  unit
#  Further  RL  +  Rx  =  sqrt(5)*a/4,  solving  for  Rx
#  Radius of the largest sphere  that will fit into the octahedral void, unit
Rx  =  (5)**0.5*a/4-RL;

#Result

print"\nThe  radius  of  the  largest  sphere "
print " that  will  fit  into  the  tetrahedral  void  is  :",round(Rx,2),"RL"

The  radius  of  the  largest  sphere
that  will  fit  into  the  tetrahedral  void  is  : 0.29 RL

## Exa 3.5¶

In [5]:
from __future__ import division
import math
#Python  Code  Ex3.5  Diameter  of  the  largest  atom  that
# would  fit  into  the  tetrahedral  void:5  Page-101  (2010)

#Variable declaration

a  =  3.52*10**-10;                #  Lattice  parameter  for  Ni,  m

#Calculations

#  For  an  fcc  lattice,  sqrt(2)*a  =  4*R,  solving  for  R
R  =  (2)**0.5*a/4;          #  Radius  of  the  atom  in  fcc  lattice,  m
R_oct  =  0.414*R; #Radius of the octahedral void  in  fcc  close  packing, m
D  =  2*R_oct#Diameter of the octahedral void in the fcc structure of nickel,m

#Result

print"The diameter of the octahedral void in the fcc structure of nickel,"
print" in angstrom, is : ",round(D/(1*10**-10),2)

The diameter of the octahedral void in the fcc structure of nickel,
in angstrom, is :  1.03

## Exa 3.6¶

In [6]:
from __future__ import division
import math
# Python Code Ex3.6 Void space in cubic close packing:  Page-101  (2010)

#Variable declaration

R  =  1;               #  For  simplicity,  radius  of  the  sphere,  m
n  =  4;                 #  Number  of  lattice  points  in  fcc  unit  cell

#Calculations

#  For  cubic  close  packing,  side  of  the  unit  cell
#and  the  radius  of  the  sphere  is  related  as
#        sqrt(2)*a  =  4*R,  solving  for  a
a  =  2*(2)**0.5*R;     #Lattice  parameter  for  cubic  close  packing,  m
V_cell  =  a**3;                         #  Volume  of  the  unit  cell
#  Volume  occupied  by  the  atoms,  metre  cube
V_occupied  =  4*4/3*math.pi*((1.000)**3+(0.414)**3+2*(0.225)**3);
void_space  =  V_cell  -  V_occupied; #  Void  space  in  the  close  packing
percent_void  =  void_space/V_cell*100;     #  Percentage  void  space

#Result

print"\nVoid  space  in  the  close packing is:",round(percent_void),"percent"

Void  space  in  the  close packing is: 19.0 percent

## Exa 3.7¶

In [7]:
from __future__ import division
import math
#Python CodeEx3.7 The minimum value of radius ratio in AX-compound:Page-104

#Variable declaration

# For simplicity we may assume a = 1
a = 1;                            # Lattice parameter of the crystal, unit

# Calculation

b = 2/3*a*math.sin(math.pi/3);        # Lattice parameter of the crystal, unit
# Here a = 2*Rx, where a is the lattice parameter and
# Rx is the radius of X-ions representing the bigger spheres, solving for Rx
Rx = 0.5*a;
# Also b = RA + Rx, solving for RA
RA = b - Rx;          # Radius of A-ion representing teh smaller sphere, unit

 Minimum value of radius ratio in AX compound is : 0.15


text:
# Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^N x^n$

Why does the following hold:

$$\begin{equation*} \displaystyle \sum\limits_{n=0}^{\infty} 0.7^n=\frac{1}{1-0.7} = 10/3\quad ? \end{equation*}$$

Can we generalize the above to

$$\displaystyle \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$ ?

Are there some values of $$x$$ for which the above formula is invalid?

What about if we take only a finite number of terms? Is there a simpler formula?

$$\displaystyle \sum_{n=0}^{N} x^n$$

Is there a name for such a sequence?

This is being repurposed in an effort to cut down on duplicates, see here: Coping with abstract duplicate questions.

and here: List of abstract duplicates.

By definition, a "series" (an "infinite sum") $$\sum_{n=k}^{\infty} a_n$$ is defined to be a limit, namely $$\sum_{n=k}^{\infty} a_n= \lim_{N\to\infty} \sum_{n=k}^N a_n.$$ That is, the "infinite sum" is the limit of the "partial sums", if this limit exists. If the limit exists, equal to some number $S$, we say the series "converges" to the limit, and we write $$\sum_{n=k}^{\infty} a_n = S.$$ If the limit does not exist, we say the series diverges and is not equal to any number.

So writing that $$\sum_{n=0}^{\infty} 0.7^n = \frac{1}{1-0.7}$$ means that we are asserting that $$\lim_{N\to\infty} \sum_{n=0}^N0.7^n = \frac{1}{1-0.7}.$$

So what your question is really asking is: why is this limit equal to $\frac{1}{1-0.7}$? (Or rather, that is the only way to make sense of the question).

In order to figure out the limit, it is useful (but not strictly necessary) to have a formula for the partial sums, $$s_N = \sum_{n=0}^N 0.7^n.$$ This is where the formulas others have given come in. If you take the $N$th partial sum and multiply by $0.7$, you get $$\begin{array}{rcrcrcrcrcrcl} s_N &= 1 &+& (0.7) &+& (0.7)^2 &+& \cdots &+& (0.7)^N\\ (0.7)s_N &= &&(0.7) &+& (0.7)^2 &+&\cdots &+&(0.7)^N &+& (0.7)^{N+1} \end{array}$$ so that $$(1-0.7)s_N = s_N - (0.7)s_N = 1 - (0.7)^{N+1}.$$ Solving for $s_N$ gives $$s_N = \frac{1 - (0.7)^{N+1}}{1-0.7}.$$ What is the limit as $N\to\infty$? The only part of the expression that depends on $N$ is $(0.7)^{N+1}$. Since $|0.7|\lt 1$, then $\lim\limits_{N\to\infty}(0.7)^{N+1} = 0$. So, $$\lim_{N\to\infty}s_N = \lim_{N\to\infty}\left(\frac{1-(0.7)^{N+1}}{1-0.7}\right) = \frac{\lim\limits_{N\to\infty}1 - \lim\limits_{N\to\infty}(0.7)^{N+1}}{\lim\limits_{N\to\infty}1 - \lim\limits_{N\to\infty}0.7} = \frac{1 - 0}{1-0.7} = \frac{1}{1-0.7}.$$ Since the limit exists, then we write $$\sum_{n=0}^{\infty}(0.7)^n = \frac{1}{1-0.7}.$$

More generally, a sum of the form $$a + ar + ar^2 + ar^3 + \cdots + ar^k$$ with $a$ and $r$ constant is said to be a "geometric series" with initial term $a$ and common ratio $r$. If $a=0$, then the sum is equal to $0$. If $r=1$, then the sum is equal to $(k+1)a$. If $r\neq 1$, then we can proceed as above. Letting $$S = a +ar + \cdots + ar^k$$ we have that $$S - rS = (a+ar+\cdots+ar^k) - (ar+ar^2+\cdots+a^{k+1}) = a - ar^{k+1}$$ so that $$(1-r)S = a(1 - r^{k+1}).$$ Dividing through by $1-r$ (which is not zero since $r\neq 1$), we get $$S = \frac{a(1-r^{k+1})}{1-r}.$$

A series of the form $$\sum_{n=0}^{\infty}ar^{n}$$ with $a$ and $r$ constants is called an infinite geometric series. If $r=1$, then $$\lim_{N\to\infty}\sum_{n=0}^{N}ar^{n} = \lim_{N\to\infty}\sum_{n=0}^{N}a = \lim_{N\to\infty}(N+1)a = \infty,$$ so the series diverges. If $r\neq 1$, then using the formula above we have: $$\sum_{n=0}^{\infty}ar^n = \lim_{N\to\infty}\sum_{n=0}^{N}ar^{N} = \lim_{N\to\infty}\frac{a(1-r^{N+1})}{1-r}.$$ The limit exists if and only if $\lim\limits_{N\to\infty}r^{N+1}$ exists. Since $$\lim_{N\to\infty}r^{N+1} = \left\{\begin{array}{ll} 0 &\mbox{if |r|\lt 1;}\\ 1 & \mbox{if r=1;}\\ \text{does not exist} &\mbox{if r=-1 or |r|\gt 1} \end{array}\right.$$ it follows that: \begin{align*} \sum_{n=0}^{\infty}ar^{n} &=\left\{\begin{array}{ll} 0 &\mbox{if a=0;}\\ \text{diverges}&\mbox{if a\neq 0 and r=1;}\\ \lim\limits_{N\to\infty}\frac{a(1-r^{N+1})}{1-r} &\mbox{if r\neq 1;}\end{array}\right.\\ &= \left\{\begin{array}{ll} \text{diverges}&\mbox{if a\neq 0 and r=1;}\\ \text{diverges}&\mbox{if a\neq 0, and r=-1 or |r|\gt 1;}\\ \frac{a(1-0)}{1-r}&\mbox{if |r|\lt 1;} \end{array}\right.\\ &=\left\{\begin{array}{ll} \text{diverges}&\mbox{if a\neq 0 and |r|\geq 1;}\\ \frac{a}{1-r}&\mbox{if |r|\lt 1.} \end{array}\right. \end{align*}

Your particular example has $a=1$ and $r=0.7$.

Since this recently came up (09/29/2011), let's provide a formal proof that $$\lim_{N\to\infty}r^{N+1} = \left\{\begin{array}{ll} 0 &\mbox{if |r|\lt 1;}\\ 1 & \mbox{if r=1;}\\ \text{does not exist} &\mbox{if r=-1 or |r|\gt 1} \end{array}\right.$$

If $r\gt 1$, then write $r=1+k$, with $k\gt0$. By the binomial theorem, $r^n = (1+k)^n \gt 1+nk$, so it suffices to show that for every real number $M$ there exists $n\in\mathbb{N}$ such that $nk\gt M$. This is equivalent to asking for a natural number $n$ such that $n\gt \frac{M}{k}$, and this holds by the Archimedean property; hence if $r\gt 1$, then $\lim\limits_{n\to\infty}r^n$ does not exist. From this it follows that if $r\lt -1$ then the limit also does not exist: given any $M$, there exists $n$ such that $r^{2n}\gt M$ and $r^{2n+1}\lt M$, so $\lim\limits_{n\to\infty}r^n$ does not exist if $r\lt -1$.

If $r=-1$, then for every real number $L$ either $|L-1|\gt \frac{1}{2}$ or $|L+1|\gt \frac{1}{2}$. Thus, for every $L$ and for every $M$ there exists $n\gt M$ such that $|L-r^n|\gt \frac{1}{2}$ proving the limit cannot equal $L$; thus, the limit does not exist. If $r=1$, then $r^n=1$ for all $n$, so for every $\epsilon\gt 0$ we can take $N=1$, and for all $n\geq N$ we have $|r^n-1|\lt\epsilon$, hence $\lim\limits_{N\to\infty}1^n = 1$. Similarly, if $r=0$, then $\lim\limits_{n\to\infty}r^n = 0$ by taking $N=1$ for any $\epsilon\gt 0$.

Next, assume that $0\lt r\lt 1$. Then the sequence $\{r^n\}_{n=1}^{\infty}$ is strictly decreasing and bounded below by $0$: we have $0\lt r \lt 1$, so multiplying by $r\gt 0$ we get $0\lt r^2 \lt r$. Assuming $0\lt r^{k+1}\lt r^k$, multiplying through by $r$ we get $0\lt r^{k+2}\lt r^{k+1}$, so by induction we have that $0\lt r^{n+1}\lt r^n$ for every $n$.

Since the sequence is bounded below, let $\rho\geq 0$ be the infimum of $\{r^n\}_{n=1}^{\infty}$. Then $\lim\limits_{n\to\infty}r^n =\rho$: indeed, let $\epsilon\gt 0$. By the definition of infimum, there exists $N$ such that $\rho\leq r^N\lt \rho+\epsilon$; hence for all $n\geq N$, $$|\rho-r^n| = r^n-\rho \leq r^N-\rho \lt\epsilon.$$ Hence $\lim\limits_{n\to\infty}r^n = \rho$.

In particular, $\lim\limits_{n\to\infty}r^{2n} = \rho$, since $\{r^{2n}\}_{n=1}^{\infty}$ is a subsequence of the converging sequence $\{r^n\}_{n=1}^{\infty}$. On the other hand, I claim that $\lim\limits_{n\to\infty}r^{2n} = \rho^2$: indeed, let $\epsilon\gt 0$. Then there exists $N$ such that for all $n\geq N$, $r^n - \rho\lt\epsilon$. Moreover, we can assume that $\epsilon$ is small enough so that $\rho+\epsilon\lt 1$. Then $$|r^{2n}-\rho^2| = |r^n-\rho||r^n+\rho| = (r^n-\rho)(r^n+\rho)\lt (r^n-\rho)(\rho+\epsilon) \lt r^n-\rho\lt\epsilon.$$ Thus, $\lim\limits_{n\to\infty}r^{2n} = \rho^2$. Since a sequence can have only one limit, and the sequence of $r^{2n}$ converges to both $\rho$ and $\rho^2$, then $\rho=\rho^2$. Hence $\rho=0$ or $\rho=1$. But $\rho=\mathrm{inf}\{r^n\mid n\in\mathbb{N}\} \leq r \lt 1$. Hence $\rho=0$.

Thus, if $0\lt r\lt 1$, then $\lim\limits_{n\to\infty}r^n = 0$.

Finally, if $-1\lt r\lt 0$, then $0\lt |r|\lt 1$. Let $\epsilon\gt 0$. Then there exists $N$ such that for all $n\geq N$ we have $|r^n| = ||r|^n|\lt\epsilon$, since $\lim\limits_{n\to\infty}|r|^n = 0$. Thus, for all $\epsilon\gt 0$ there exists $N$ such that for all $n\geq N$, $| r^n-0|\lt\epsilon$. This proves that $\lim\limits_{n\to\infty}r^n = 0$, as desired.

In summary, $$\lim_{N\to\infty}r^{N+1} = \left\{\begin{array}{ll} 0 &\mbox{if |r|\lt 1;}\\ 1 & \mbox{if r=1;}\\ \text{does not exist} &\mbox{if r=-1 or |r|\gt 1} \end{array}\right.$$

The argument suggested by Srivatsan Narayanan in the comments to deal with the case $0\lt|r|\lt 1$ is less clumsy than mine above: there exists $a\gt 0$ such that $|r|=\frac{1}{1+a}$. Then we can use the binomial theorem as above to get that $$|r^n| = |r|^n = \frac{1}{(1+a)^n} \leq \frac{1}{1+na} \lt \frac{1}{na}.$$ By the Archimedean Property, for every $\epsilon\gt 0$ there exists $N\in\mathbb{N}$ such that $Na\gt \frac{1}{\epsilon}$, and hence for all $n\geq N$, $\frac{1}{na}\leq \frac{1}{Na} \lt\epsilon$. This proves that $\lim\limits_{n\to\infty}|r|^n = 0$ when $0\lt|r|\lt 1$, without having to invoke the infimum property explicitly.

• I think we should use this question for a generalization. The above answer already has an answer to the general version. Mar 31 '11 at 16:58
• Arturo, I will mention one more way of proving that $r^n$ converges to $0$ as $n \to \infty$ if $|r| < 1$ that looks somewhat similar to your proof in the divergent case. Take $|r| = \frac{1}{1+a}$ for some $a > 0$. Then $$|r^n - 0| = |r|^n = \frac{1}{(1+a)^n} \leq \frac{1}{1+an} \leq \frac{1}{an} ,$$ which can be made sufficiently small by taking $n$ large enough. Sep 30 '11 at 4:13
• When you say that the limit of the partial sums of a geometric series exists iff the limit of $r^{N+1}$ exists, that's wrong, because it still diverges (as you state later) when $r=1$. Jun 7 '13 at 21:49

it's called a geometric series. let $$-1 and let $$S_n=1+x+x^2+...+x^n$$. then $$xS_n=x+...+x^{n+1}=S_n-1+x^{n+1}$$. move stuff around to get $$S_n=\frac{1-x^{n+1}}{1-x}$$ take the limit as $$n\to\infty$$ (noting that $$x^n\to0$$ if $$|x|<1$$)

• In yoyo's answer, you should also take into account that $x^{n+1}\to 0$ as $n\to\infty$ if $|x| < 1$. Mar 25 '11 at 16:48
• Btw we could also do (instead of taking $xS_n$) $S_n := 1 + x + \dots + x^n = 1 + x(1 + x + \dots + x^{n-1}) = 1 + xS_{n-1} = 1 + x(S_n - x^n)$, giving $S_n = 1 + x(S_n - x^n)$ Apr 16 '21 at 12:53

$$\frac{1}{1-x}=(1-x)^{-1}\\=1+{-1\choose1}(-x)+{-1\choose2}(-x)^2+{-1\choose3}(-x)^3...\\=1+x+x^2+x^3+...,$$

which is a geometric series.

• Haha, a unique little jewel in the rough that ought've had more attention. Dec 30 '16 at 16:35

If u expand your summation you get series $$1+0.7+0.7^2+\dots$$ as it is geometric series (you can see it here http://en.wikipedia.org/wiki/Geometric_series) $$\sum_{n=0}^{\infty}{0.7^n}=\frac{1}{1-0.7}$$

Or $S=1+x+x^2+\dots$

$xS_n=x+x^2+\dots=S-1$ now u take

$S-xS=1$

$S(1-x)=1 \implies S=\frac{1}{1-x}$

here your $x=0.7$

I find the proof here lovely.

• @BabyDragon Here is the updated link. Oct 6 '13 at 9:12

Using the fact that $$x^n - y^n=(x-y)\sum_{k=1}^nx^{k-1}y^{n-k}$$

Set $$x=1$$ and $$y \in \mathbb{N}$$ to get the desired result.

$$1 - y^n=(1-y)\sum_{k=1}^ny^{n-k} \iff \sum_{k=1}^ny^{n-k}=y^n\sum_{k=1}^ny^{-k}=\frac{y^n-1}{y-1} \iff \sum_{k=1}^n \frac{1}{y^k} = \frac{y^n-1}{y^{n+1}-y^n}$$

Now, using the limit of the result we have $$\large{\lim_{n\to \infty}\frac{y^n-1}{y^{n+1}-y^n} = \frac{1}{y-1}}$$.

Some examples,

$$\sum_{k=1}^\infty \left(\frac{1}{2}\right)^k = 1$$ $$\sum_{k=1}^\infty \left(\frac{1}{3}\right)^k = 1/2$$ $$\sum_{k=1}^\infty \left(\frac{1}{4}\right)^k = 1/3$$ $$\sum_{k=1}^\infty \left(\frac{1}{5}\right)^k = 1/4$$

Also, if $$y \to \infty \implies$$

$$\sum_{k=1}^\infty \left(\frac{1}{y}\right)^k = 0$$

format: plain


text:
Subject:
Calculus
Material Type:
Module
Provider:
Ohio Open Ed Collaborative
Tags:
Cac077, Calculus, First Fundamental Theorem of Calculus
Language:
English
Media Formats:
eBook, Interactive

# First fundamental theorem of calculus modules

## Overview

After completing this section, students should be able to do the following.

• Define accumulation functions.
• Calculate and evaluate accumulation functions.
• State the First Fundamental Theorem of Calculus.
• Take derivatives of accumulation functions using the First Fundamental Theorem of Calculus.
• Use accumulation functions to find information about the original function.
• Understand the relationship between the function and the derivative of its accumulation function.

# What's in a calculus problem?

## Ximera Module

Two young mathematicians discuss what calculus is all about.

# The First Fundamental Theorem of Calculus

## Ximera Module

The rate that accumulated area under a curve grows is described identically by that curve.


text:
# Bibliotek

Musik » Jason Mraz »

## The World As I See It

14 spelade låtar | Gå till låtsida

Från söndag 18 mars 2012 till onsdag 18 april 2012 Alltid

Låtar (14)
Låt Album Längd Datum
The World As I See It 8:34 18 apr 2012, 09:07
The World As I See It 8:34 16 apr 2012, 12:52
The World As I See It 8:34 11 apr 2012, 05:33
The World As I See It 8:34 11 apr 2012, 04:16
The World As I See It 8:34 1 apr 2012, 14:28
The World As I See It 8:34 29 mar 2012, 18:40
The World As I See It 8:34 28 mar 2012, 17:20
The World As I See It 8:34 26 mar 2012, 13:11
The World As I See It 8:34 26 mar 2012, 11:54
The World As I See It 8:34 25 mar 2012, 15:02
The World As I See It 8:34 23 mar 2012, 17:24
The World As I See It 8:34 21 mar 2012, 03:07
The World As I See It 8:34 21 mar 2012, 03:03
The World As I See It 8:34 18 mar 2012, 16:48


text:
# Translating between the "Bivector" and "Lengyel" models of PGA

Loosely, there seem to be at least two different notations & jargons for describing geometric objects and operators in 3D PGA.

What I’m calling the “BiVector” model: the 2019 Siggraph course, alot of the discussion on Bivector.net, and the Klein library.

And the “Lengyel” model, as outlined at http://projectivegeometricalgebra.org/

As I understand it, mathematically, the two models are consistent. But there are alot of differences, both in the jargon used and also in the notation; egs Antivectors, e0 vs e4, “bulk norms”, “weight norms”, “ideal norms”, the way that Points and Planes are represented.

I’d like to develop an ability to mentally translate back and forth between the notational conventions, so as to reconcile the material in both places into one coherent system.

Does anyone have a cheat sheet for mapping between the terminology? or some pointers to how to build such a mapping…

You may or may not be looking for the hodge dual.

Assuredly, the Hodge dual lies at the heart of the differences between presentations.

What I find myself wanting is the expansion of the differences out to the various terms and operators that are mentioned, in places like the Siggraph PGA cheat sheet and Lengyel’s wiki.

To give a practical example of the sorts of questions/doubts in my mind: What Lengyel calls the Bulk Norm would be written as X in the Bivector model…? (solve for X ;P)

Meanwhile, the Siggraph materials talk about Ideal Norm, which doesnt get a mention in the Lengyel model. How does that map across?

Im actually tentatively working out the translation myself, which if nothing else is driving me to understand things better. If I reach something Im confident to share, I’ll post it here.

In Section 7.1 of the course notes, the “bivector” model defines the norm as

\Vert \mathbf x\Vert = \sqrt{|\mathbf x^2|},

where the squaring inside the radical is done with the geometric product. It defines the “ideal norm” (or “infinity norm”) in a case-by-case manner for points, lines, and pseudoscalars without providing a general formula or addressing planes, motors, and reflection operators, and it utterly fails to recognize the symmetry at work.

First, the norm as defined in the course notes isn’t quite correct. It should be

\Vert \mathbf x\Vert = \sqrt{\mathbf x\mathbf{\widetilde x}},

which gets rid of the embarrassing need for the absolute value.

In the “Lengyel” model, the “bulk norm” and “weight norm” are defined as

Bulk norm: \Vert\mathbf x\Vert_\bullet = \sqrt{\mathbf x \mathbin{\char"27D1} \mathbf{\widetilde x}}

Weight norm: \Vert\mathbf x\Vert_\circ = \sqrt{\mathbf x \mathbin{\char"27C7} \mathbf{\utilde x}\vphantom{\mathbf{\widetilde x}}} ,

where \char"27D1 is the geometric product, and \char"27C7 is the geometric antiproduct. For the objects in PGA that we care about, the bulk norm is a scalar, and the weight norm is an antiscalar (pseudoscalar).

The “ideal norm” is mathematically the same as the weight norm, but (incorrectly) dualized to be a scalar instead of an antiscalar. Unfortunately, it cannot be expressed quite as symmetrically because the “bivector” model lacks the antiproduct, but you could write

Ideal norm: \Vert\mathbf x\Vert_\infty = \sqrt{\mathbf x^*\widetilde{\mathbf x^*}} ,

where * is any dualization operator.

Note that because the “bivector” model describes geometries and isometry operators with empty dimensions instead of full dimensions, the meaning of the two norms is reversed. So the “bivector” norm gives you the magnitude of the weight of an object, and the ideal norm gives you the magnitude of its bulk. (Or to use the terminology suggested by the “bivector” crowd, the norm gives you the magnitude of the tangent space aspect of the object, and the ideal norm gives you the magnitude of its positional aspect.)

The projected magnitude or geometric norm of an object \mathbf x, which is the distance from the origin for something regarded as a geometry and half the distance the origin is moved for something regarded as an isometry operator, is given by the ratio of the norms. Using the notation m(\mathbf x) for the projected magnitude here to avoid conflicts with other notation, in the “bivector” model,

m(\mathbf x) = \dfrac{\Vert\mathbf x\Vert_\infty}{\Vert\mathbf x\Vert} = \dfrac{\sqrt{\mathbf x^*\widetilde{\mathbf x^*}}}{\sqrt{\mathbf x\mathbf{\widetilde x}}} ,

and in the “Lengyel” model,

m(\mathbf x) = \dfrac{\Vert\mathbf x\Vert_\bullet}{\Vert\mathbf x\Vert_\circ} = \dfrac{\sqrt{\mathbf x \mathbin{\char"27D1} \mathbf{\widetilde x}}}{\sqrt{\mathbf x \mathbin{\char"27C7} \mathbf{\utilde x}\vphantom{\mathbf{\widetilde x}}}} .

(Note: with the appropriate definitions of wedge and dot products involving scalars, all of the geometric products above can be replaced with dot products and antidot products.)

1 Like

Hi @elengyel
Thanks for the detailed comments regarding the ideal norm.
First, a quick feedback regarding the course notes. Since February, 2020, motivated partly by a discussion on this forum, the section in the course notes on the ideal norm has included a subsection entitled “Ideal norm via Poincare duality” which I include here:

Another neat way to compute the ideal norm is provided by Poincare duality. The discussion of Poincare duality above … took place at the level of the Grassmann algebra. It’s possible to consider this map to be between geometric algebras, in this case, J: P(\mathbb{R}^*_{2,0,1})\rightarrow P(\mathbb{R}_{2,0,1}). We leave it as an exercise for the reader to verify that for ideal \mathbf{x} \in P(\mathbb{R}^*_{2,0,1}), \| \mathbf{x} \|_\infty = \| J(\mathbf{x})\| (where by sleight-of-hand the scalar on the right-hand side is interpreted as a scalar in P(\mathbb{R}^*_{2,0,1})). That is, the ideal norm in the euclidean plane is the ordinary norm in the dual euclidean plane. Naturally the same holds for arbitrary dimension. Whether this \quot{trick} has a deeper meaning remains a subject of research.

(Perhaps you have an older copy? I’m constantly updating them as my views on the subject develop. Best place to remain updated is https://arxiv.org/abs/2002.04509.)

Note that this section also addresses the issue of whether the ideal norm should be considered a pseudoscalar or a scalar in the original algebra and acknowledges the need for further research, exactly the sort which your post contains.

I have been planning for weeks to post a reply to the original message on this thread: I think it’s misleading to refer to a monolithic “bivector” model: there are some quite sharp differences among the views represented there. And if and when I get around to that, I’ll try to address the interesting points you make regarding the bulk and weight norms.

1 Like


text:
## Homology, Homotopy and Applications

### Trees, free right-symmetric algebras, free Novikov algebras and identities

#### Abstract

An algebra with the identity $x\circ (y\circ z-z\circ y)= (x\circ y)\circ z-(x\circ z)\circ y$ is called right-symmetric. A right-symmetric algebra with the identity $x\circ(y\circ z)= y\circ(x\circ z)$ is called Novikov. We describe bases of free right-symmetric algebras and free Novikov algebras and give realizations of them in terms of trees. The free Lie algebra is obtained as a Lie subalgebra of the free right-symmetric algebra. We use our methods to study identities of Witt algebras.

#### Article information

Source
Homology Homotopy Appl., Volume 4, Number 2 (2002), 165-190.

Dates
First available in Project Euclid: 13 February 2006

https://projecteuclid.org/euclid.hha/1139852461

Mathematical Reviews number (MathSciNet)
MR1918188

Zentralblatt MATH identifier
1029.17001

Subjects
Primary: 17A30: Algebras satisfying other identities

#### Citation

Dzhumadiľdaev, Askar; Löfwall, Clas. Trees, free right-symmetric algebras, free Novikov algebras and identities. Homology Homotopy Appl. 4 (2002), no. 2, 165--190. https://projecteuclid.org/euclid.hha/1139852461


text:
# $A$ has measure $0$

I've got the following problem... We are given a sequence of integers $n_k\to+\infty$ as $k\to\infty$. Then we define $$A:=\{x\in[0,2\pi]\,\colon\,\lim_{k\to\infty}\sin(n_kx) \text{ exists}\}.$$

I have to prove now that $\operatorname{meas}(A)=0$, where the measure is the usual Lebesgue measure on the real line.

I've proved the following relation which I assume can be useful for the sequel, namely for any measurable $B\subseteq A$, setting $$f(x):=\lim_{k\to\infty}\sin(n_kx),$$ it follows $$\int_B 2(f(x))^2\mathrm dx=\lim_{k\to\infty}\int_B1-\cos(n_kx)\mathrm dx=\operatorname{meas}(B).$$ Then $A$ is measurable (I have proved it), so I want to apply the previous result: my plan is to show that $f(x)$ must be almost everywhere $0$ but I cannot see a neat argument.

Another strategy I've thought about would be to reason by contradiction and see what happen if $A$ has strictly positive measure. At any rate this way seems nice to me because the result in this case would imply that $f$ must be equal to $0$ almost everywhere on $A$ in contrast with the previous way which uses this conclusion as the starting assumption.

In any case, I've spent quite a lot of time on this without success, so I'm asking you to help me...

-Guido-

-
I think it suffices to prove that if $\lim\sin(n_k x)$ exists then it is zero. You can argue this by contradiction. Then it's fairly clear that $A$ has measure zero, since it's merely a countable set of points. If anything's unclear let me know, and I'll write it up in full below! –  Edward Hughes Jun 11 '12 at 12:49
but what if, for example, $n_k=4k+1$ and $x=\frac\pi2$? In this case the limit exists and it is constantly $1$ so I cannot claim that if the limit exists then it is $0$. I don't get your point sorry... –  guido giuliani Jun 11 '12 at 13:11
Oh yes damn, sorry that doesn't work. I think I was halfway to something more like Siminore has written below, but didn't quite think it through! –  Edward Hughes Jun 11 '12 at 13:29

1. Prove that $$\lim_{n \to +\infty} \int_E \sin nx \, dx = \lim_{n \to +\infty} \int_E \cos nx \, dx =0$$ for every measurable subset $E$ of $[0,2\pi]$. Hint: Riemann-Lebesgue.
2. Assume that the subsequence $\{\sin n_k x\}_k$ converges. Since $2 \sin^2 \alpha = 1 -\cos 2\alpha$, we deduce from the previous step that $\sin n_k x \to \pm \frac{1}{\sqrt{2}}$ almost everywhere.
you mean... $\sin(n_kx)\to\pm\frac{1}{\sqrt2}$? –  guido giuliani Jun 11 '12 at 13:27


text:
Hardcover | $47.00 Short | £34.95 | ISBN: 9780262016841 | 388 pp. | 6 x 9 in | 3 b&w illus. | January 2012 eBook |$31.00 Short | ISBN: 9780262302296 | 388 pp. | 3 b&w illus. | January 2012

## Heidegger and the Thinking of Place

Explorations in the Topology of Being

## Overview

The idea of place--topos--runs through Martin Heidegger’s thinking almost from the very start. It can be seen not only in his attachment to the famous hut in Todtnauberg but in his constant deployment of topological terms and images and in the situated, “placed” character of his thought and of its major themes and motifs. Heidegger’s work, argues Jeff Malpas, exemplifies the practice of “philosophical topology.” In Heidegger and the Thinking of Place, Malpas examines the topological aspects of Heidegger’s thought and offers a broader elaboration of the philosophical significance of place. Doing so, he provides a distinct and productive approach to Heidegger as well as a new reading of other key figures--notably Kant, Aristotle, Gadamer, and Davidson, but also Benjamin, Arendt, and Camus.

Malpas, expanding arguments he made in his earlier book Heidegger’s Topology (MIT Press, 2007), discusses such topics as the role of place in philosophical thinking, the topological character of the transcendental, the convergence of Heideggerian topology with Davidsonian triangulation, the necessity of mortality in the possibility of human life, the role of materiality in the working of art, the significance of nostalgia, and the nature of philosophy as beginning in wonder. Philosophy, Malpas argues, begins in wonder and begins in place and the experience of place. The place of wonder, of philosophy, of questioning, he writes, is the very topos of thinking.

Jeff Malpas is Distinguished Professor at the University of Tasmania and Distinguished Visiting Professor at Latrobe University. He is the author of Heidegger’s Topology: Being, Place, World and Heidegger and the Thinking of Place: Explorations in the Topology of Being, both published by the MIT Press.

## Reviews

“A brilliant job....This book constitutes another impressive achievement by Jeff Malpas in reconsidering the importance and sense of place, not only Heidegger's work, but also more broadly in philosophy itself.”—Notre Dame Philosophical Reviews

## Endorsements

“Jeff Malpas's Heidegger and the Thinking of Place is a powerful companion volume of essays to his earlier Heidegger's Topology, but can also stand alone as an introduction to the crucial theme of place in Heidegger's work. Especially powerful is the triptych of essays in the third part on nostalgia, death, and truth, which move from the thinking of place to thinking through place. Malpas's ongoing dialogue with Heidegger goes to the heart of both thinker's concerns, and demonstrates Malpas's ability both to discuss complicated questions clearly and to show the complications in what previously appeared clear.”
Stuart Elden, Professor of Political Geography, Durham University
Heidegger and The Thinking of Place not only confirms Jeff Malpas as a central interpreter of Heidegger, it reinforces his position as one of the most significant philosophers writing on the concept of place today. Henceforth it will be impossible to work on either 'topos' or 'place' without talking Malpas's writings as the point of departure. Malpas works between and across traditions. If philosophy is to have a future that lifts it beyond the confines of commentary on the one hand or political posturing on the other then it is work by a philosopher such as Jeff Malpas that will show the way.”
Andrew Benjamin, Professor of Critical Theory and Philosophical Aesthetics, Director Research Unit in European Philosophy, Monash University
“Almost single-handedly, Jeff Malpas has created a new philosophical topic, that of 'place'. Heidegger and the Thinking of Place far exceeds the bounds of Heidegger exegesis. It is a major work by the most original philosopher working in Australasia today.”
Julian Young, Kenan Professor of Humanities, Wake Forest University


text:
# 12.4: Exchange Rate Policy with Fixed Exchange Rates

• Contributed by No Attribution by request
• Anonymous by request

Learning objectives

1. Learn how changes in exchange rate policy affect GNP, the value of the exchange rate, and the current account balance in a fixed exchange rate system in the context of the AA-DD model.
2. Understand the adjustment process in the money market, the Forex market, and the G&S market.

In this section, we use the AA-DD model to assess the effects of exchange rate policy in a fixed exchange rate system. In a sense we can say that the government’s decision to maintain a fixed exchange is the country’s exchange rate policy. However, over time, the government does have some discretion concerning the value of the exchange rate. In this section, we will use “exchange rate policy” to mean changes in the value of the fixed exchange rate.

If the government lowers the value of its currency with respect to the reserve currency or to gold, we call the change a devaluation. If the government raises the value of its currency with respect to the reserve currency or to gold, we call the change a revaluation. The terms devaluation and revaluation should properly be used only in reference to a government change in the fixed exchange rate since each term suggests an action being taken. In contrast, natural market changes in supply and demand will result in changes in the exchange rate in a floating system, but it is not quite right to call these changes devaluations or revaluations since no concerted action was taken by anyone. Nonetheless, some writers will sometimes use the terms this way.

In most cases, devaluations and revaluations occur because of persistent balance of payments disequilibria. We will consider these situations in Chapter 12 "Policy Effects with Fixed Exchange Rates", Section 12.6 "Currency Crises and Capital Flight" on balance of payments crises and capital flight. In this section, we will consider the basic effects of devaluations and revaluations without assuming any notable prior events caused these actions to occur.

Suppose the United States fixes its exchange rate to the British pound at the rate $$Ē_{/£}$$. This is indicated in Figure 12.4.1 as a horizontal line drawn at $$Ē_{/£}$$. Suppose also that the economy is originally at a superequilibrium shown as point F with gross national product (GNP) at level $$Y^{1}$$. Next, suppose the U.S. central bank (or the Fed) decides to devalue the U.S. dollar with respect to the British pound corresponding to an increase in the fixed rate from $$Ē_{/£}$$ to $$Ê_{/£}$$. Recall that a devaluation corresponds to an increase in the $/£ exchange rate. Assume that there was no anticipation of the devaluation and that it comes about as a complete surprise to all market participants. Figure $$\PageIndex{1}$$: Effects of a Devaluation The first effect of the devaluation, of course, is that the exchange rate rises. Immediately the economy moves from F to G on the diagram. It may seem that this would move the economy off the AA curve, but instead the AA curve shifts up with the devaluation to A′A′. This occurs because the AA curve is a function of the expected exchange rate. As long as investors believe that the new exchange rate will now remain fixed at its new rate ($$Ê_{/£}$$), the expected future exchange rate will immediately rise to this new level as well. It is this increase in $$E_{/£}^{e}$$ that causes AA to shift up. When at point G, however, the economy is not at a superequilibrium. Because of the dollar devaluation, the real exchange rate has increased, making foreign goods relatively more expensive and U.S. goods relatively cheaper. This raises aggregate demand, which at the new exchange rate ($$Ê_{/£}$$) is now at the level where the exchange rate line crosses the DD curve at point H. Since the economy, for now, lies at G to the left of point H on the DD curve, aggregate demand exceeds supply. Producers will respond by increasing supply to satisfy the demand, and GNP will begin to rise. As GNP rises, real money demand will rise, causing an increase in U.S. interest rates, which will raise the rate of return on U.S. assets. Investors will respond by increasing their demand for U.S. dollars on the foreign exchange (Forex) market, and there will be pressure for a dollar appreciation. To maintain the fixed exchange rate, however, the U.S. Fed will have to automatically intervene on the Forex and sell dollars to satisfy the excess demand in exchange for pounds. This represents a balance of payments surplus since by buying pounds on the Forex the United States is adding to its stock of foreign reserves. A balance of payments surplus in turn causes an increase in the U.S. money supply, which will shift the AA curve to the right. As GNP rises toward $$Y^{2}$$ at point H, the AA curve will shift right with the Fed intervention to maintain the equilibrium exchange rate at the new fixed value, which is $$Ê_{/£}$$. The final superequilibrium occurs at point H where excess aggregate demand is finally satisfied. The final result is that a devaluation in a fixed exchange rate system will cause an increase in GNP (from $$Y^{1}$$ to $$Y^{2}$$) and an increase in the exchange rate to the new fixed value in the short run. Since the new equilibrium at H lies above the original CC curve representing a fixed current account balance, a devaluation will cause the current account balance to rise. This corresponds to an increase in a trade surplus or a decrease in a trade deficit. ## Revaluation A revaluation corresponds to change in the fixed exchange rate such that the country’s currency value is increased with respect to the reserve currency. In the AA-DD model, a U.S. dollar revaluation would be represented as a decrease in the fixed$/£ exchange rate. The effects will be the opposite of those described above for a devaluation. A complete description is left for the reader as an exercise.

The quick effects, however, are as follows. A revaluation in a fixed exchange rate system will cause a decrease in GNP and a decrease in the fixed exchange rate in the short run. A revaluation will also cause the current account balance to fall. This corresponds to a decrease in a trade surplus or an increase in a trade deficit.

key Takeaways

• If the government lowers (raises) the value of its currency with respect to the reserve currency, or to gold, we call the change a devaluation (revaluation).
• A devaluation in a fixed exchange rate system will cause an increase in GNP, an increase in the exchange rate to the new fixed value in the short run, and an increase in the current account balance.
• A revaluation in a fixed exchange rate system will cause a decrease in GNP, an increase in the currency value to the new fixed rate, and a decrease in the current account balance.

exercises

1. Vietnam fixes its currency, the Vietnamese dong (VND), to the US dollar. Suppose Vietnam can be described using the AA-DD model. Consider changes in the exogenous variables in Vietnam in the left column. Suppose each change occurs ceteris paribus. Indicate the short-run effects on the equilibrium values of Vietnamese GNP, the Vietnamese interest rate ($$i_{VND}$$), the Vietnamese trade deficit, and the exchange rate ($$E_{VND//}$$). Use the following notation:

+ the variable increases

the variable decreases

0 the variable does not change

A the variable change is ambiguous (i.e., it may rise, it may fall)

GNP $$i_{VND}$$ $$E_{VND//}$$
A devaluation of the Vietnamese dong
A revaluation of the Vietnamese dong
2. Consider the following occurrences. Use the AA-DD model to determine the impact on the variables (+, −, 0, or A) from the twin-deficit identity listed along the top row. Consider only short-run effects (i.e., before inflationary effects occur) and assume ceteris paribus for all other exogenous variables.
Impact on
$$S_{p}$$ $$I$$ $$IM − EX$$ $$G + TR − T$$
A currency devaluation under fixed exchange rates
A currency revaluation under fixed exchange rates
3. China maintains an exchange rate fixed to the U.S. dollar at the rate $$E_{1}$$. Use the following AA-DD diagram for China to depict answers to the questions below. Suppose China’s current account is in surplus originally. Suppose $$Y_{F}$$ indicates the full employment level of output.

• Suppose China unexpectedly revalues its currency under pressure from the U.S. government. Draw a line for the new exchange rate and mark the graph with an $$E_{2}$$.
• Mark the graph with a T to indicate the position of the economy immediately after the revaluation when investor expectations adjust to the new exchange rate.
• What effect does the revaluation have for the prices of Chinese goods to Americans?
• Mark the graph with a W to indicate the position of the economy once a new short-run equilibrium is achieved. Mark the graph with $$Y_{2}$$ to indicate the new level of GDP.
• Does China’s stock of foreign reserves rise or fall after the revaluation?
• Does China’s current account surplus rise or fall?
• In the adjustment to a long-run equilibrium, would the Chinese price level rise or fall?


text:
# Accuracy of Lax-Wendroff scheme

Consider the Lax-Wendroff scheme $$\frac{u_j^{n+1}-u_j^n}{\Delta t}+\frac{u_{j+1}^n-u_{j-1}^n}{2\Delta x}+\frac{\Delta t}{2}\frac{2u_j^n-u_{j+1}^n-u_{j-1}^n}{\Delta x^2}=0$$ for differential equation $$\frac{\partial u}{\partial t}+\frac{\partial u}{\partial x}=0.$$ It's known that this scheme is second order accurate in time, $\mathcal{O}(\Delta t^2)$. How is this true since the scheme uses forward difference for time derivative? Recall that $$\frac{\partial u}{\partial t} \Big|_j^n=\frac{u_j^{n+1}-u_j^n}{\Delta t}+\mathcal{O}(\Delta t).$$ Using this observation, shouldn't this scheme be first order accurate in time, $\mathcal{O}(\Delta t)$? I have read several books on numerical analysis and the authors vaguely explain this. They use the words such as "clearly" or "obviously" instead of elaborate the derivation of the accuracy.

You can derive the consistency order of the scheme by using the Taylor expansion around (in this case) $u_j^n$. Use the expansion up to the second derivative in time (including it) and up to the third derivative in space and then note that, from the given equation, $$u_t=-u_x ~ \text{and} ~ u_{tt}=u_{xx},$$ which will help to get rid of some of the terms in the expansions. The resulting approximation order should be $\mathcal{O}(h^2+k^2)$, where $h$ is spatial step and $k$ is transient step.

If you follow the derivation of the method, you will see that it uses the Taylor expansion of order $k^3$ ($k^2$ approximation power) and $h^2$ schemes for replacing the first and second derivatives in time by spatial derivatives, which clearly indicates that the method must be $\mathcal{O}(h^2+k^2)$.


text:
# Ordinary Differential Equations!Urgent Help Neede

Printable View

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• Jun 13th 2008, 10:44 AM
noob
Quote:

Originally Posted by Isomorphism
Yes you can.

You mean "integrating factor"? There is no need for it here, since the differential equation is in separable form..

yup, what i mean is an "integrating factor"..so we only no need to consider the integrating factor when the differential equation is in separable form huh?thanks mates..really2 thanks (Nod)

i will come out with my final solution for question 1 first (still need a help in question 2 afterwards)

p/s: you are a lecturer or tutor maybe huh? sorry for off topic
• Jun 13th 2008, 10:47 AM
Isomorphism
Quote:

Originally Posted by noob
p/s: you are a lecturer or tutor maybe huh? sorry for off topic

Well... not yet (Rofl)
• Jun 14th 2008, 11:08 AM
noob
Quote:

Originally Posted by noob
Hye all, as a newbie in this forum, i would be really sorry if got any mistake or indirectly breaching the terms and condition in this forum.

I'm just really2 need a help from anyone of you, please helping me to attain the solution of both questions. The question is on Ordinary Differential Equations topic. This is my important assignment question as it will bring 15% of my career marks (continuous assessment) before final exam. Please really help as that 15% is too important to me..thanks in advanced mates (Crying)

http://i270.photobucket.com/albums/j...untitled-5.jpg

Hye again..thanks again for all your instruction, im done with no 1..now it is no 2 question

after differentiate with respect to x i obtain

$y''+ 2xy'+2y$

thus,how can i get the characteristic equation (as the initial step of using variation of parameter method) from that equation since got two variables which is x and y;

$m^2+2xy+2$

anybody help??thanks in advance

i thought is it we need to separate those x??
• Jun 14th 2008, 03:53 PM
Chris L T521
Quote:

Originally Posted by noob
thank you very much, from the question needed, is it i can left the answer just like this??one more things that quite confusing me is when did we need to consider the integral factor?? some question in book using an integral factor method

Read [in particular] post #2 (integrating factor) and #8 (variation of parameters) in my Differential Equations Tutorial. This may help with future problems.
• Jun 14th 2008, 08:07 PM
noob
Quote:

Originally Posted by Chris L T521
Read [in particular] post #2 (integrating factor) and #8 (variation of parameters) in my Differential Equations Tutorial. This may help with future problems.

i know how to use the method of variation of parameter, the problem now is how can i attain the characteristic equation since got two variables (as my previous post)..could u please help me to find it
• Jun 14th 2008, 09:13 PM
Chris L T521
Quote:

Originally Posted by noob
Hye again..thanks again for all your instruction, im done with no 1..now it is no 2 question

after differentiate with respect to x i obtain

$y''+ 2xy'+2y$

thus,how can i get the characteristic equation (as the initial step of using variation of parameter method) from that equation since got two variables which is x and y;

Quote:

Originally Posted by noob
i know how to use the method of variation of parameter, the problem now is how can i attain the characteristic equation since got two variables (as my previous post)..could u please help me to find it

Well, if the equation was $x^2\frac{d^2y}{dx^2}+2x\frac{dy}{dx}+2y=0$ then the DE has the form of a Cauchy-Euler Equation and a characteristic equation could be easily found.

However, that's not the case. Also, Mathematica and the TI-89 tell me there is no solution to the DE...(Thinking)
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12


text:
## Algebra 1: Common Core (15th Edition)

$4y−3/(y^2+1)=4/y$ cross multiply $y(4y−3)=4(y^2+1)$ distributive property $4y2−3y=4y2+4$ subtract 4y2 from each side $4y^2−3y−4y^2=4y^2+4−4y^2$ combine like terms $−3y=4$ divide both sides by -3 $−3y÷−3=4÷−3$ simplify y=−1.3333


text:
# Codes for Updating Linear Functions over Small Fields

We consider a point-to-point communication scenario where the receiver maintains a specific linear function of a message vector over a finite field. When the value of the message vector undergoes a sparse update, the transmitter broadcasts a coded version of the modified message while the receiver uses this codeword and the current value of the linear function to update its contents. It is assumed that the transmitter has access to the modified message but is unaware of the exact difference vector between the original and modified messages. Under the assumption that the difference vector is sparse and that its Hamming weight is at the most a known constant, the objective is to design a linear code with as small a codelength as possible that allows successful update of the linear function at the receiver. This problem is motivated by applications to distributed data storage systems. Recently, Prakash and Medard derived a lower bound on the codelength, which is independent of the size of the underlying finite field, and provided constructions that achieve this bound if the size of the finite field is sufficiently large. However, this requirement on the field size can be prohibitive for even moderate values of the system parameters. In this paper, we provide a field-size aware analysis of the function update problem, including a tighter lower bound on the codelength, and design codes that trade-off the codelength for a smaller field size requirement. We first characterize the family of function update problems where linear coding can provide reduction in codelength compared to a naive transmission scheme. We then provide field-size dependent bounds on the optimal codelength, and construct coding schemes when the receiver maintains linear functions of striped message vector. Finally, we show that every function update problem is equivalent to a generalized index coding problem.

## Authors

• 5 publications
• 9 publications
• ### Linear Codes for Broadcasting with Noisy Side Information

We consider network coding for a noiseless broadcast channel where each ...
01/09/2018 ∙ by Suman Ghosh, et al. ∙ 0

• ### Reduced Dimensional Optimal Vector Linear Index Codes for Index Coding Problems with Symmetric Neighboring and Consecutive Side-information

A single unicast index coding problem (SUICP) with symmetric neighboring...
01/01/2018 ∙ by Mahesh Babu Vaddi, et al. ∙ 0

• ### A Construction of Maximally Recoverable Codes with Order-Optimal Field Size

We construct maximally recoverable codes (corresponding to partial MDS c...
11/27/2020 ∙ by Han Cai, et al. ∙ 0

• ### Distributed Capacity of A Multiple Access Channel

In distributed communication, each transmitter prepares an ensemble of c...
05/07/2018 ∙ by Yanru Tang, et al. ∙ 0

• ### Explicit MSR Codes with Optimal Access, Optimal Sub-Packetization and Small Field Size for d = k+1, k+2, k+3

This paper presents the construction of an explicit, optimal-access, hig...
04/02/2018 ∙ by Myna Vajha, et al. ∙ 0

• ### Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds

Independent Component Analysis (ICA) is a statistical tool that decompos...
09/16/2018 ∙ by Amichai Painsky, et al. ∙ 0

• ### PhD Dissertation: Generalized Independent Components Analysis Over Finite Alphabets

Independent component analysis (ICA) is a statistical method for transfo...
09/13/2018 ∙ by Amichai Painsky, 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.

## I Introduction

We consider a point-to-point communication scenario as shown in Fig. 1 where the receiver maintains a linear function of a message vector . The message is an -length column vector over a finite field , where is any prime power, and A is an matrix over with and rank. Suppose the value of the message vector is updated to , where represents a sparse update to the message, i.e., we assume that where denotes the Hamming weight of a vector and is a known constant. In other words at the most entries of the original message are updated to new values. We assume that the transmitter has access to the updated message , but is unaware of the original message or the sparse update . Note that the message update is modelled here as substitutions only and not as insertions or deletions. The objective is to design a linear encoder that uses an matrix to generate the codeword , with as small a codelength as possible, such that the receiver can decode using the transmitted codeword and the older version of its content .

The problem is motivated by distributed storage systems (DSS) where information is stored in linearly coded form across a number of nodes to provide resilience against storage node failures [1]. In the scenario where multiple users can simultaneously edit a single file stored in a DSS, it is possible that a user who wishes to apply his update is unaware of the current version of the message stored in the DSS, for instance when another user has recently edited this file. Letting the user first learn the version stored in the DSS, and then apply his update will incur additional communication cost. As an alternative, if it is known that the update vector is sparse, it is possible to design schemes that do not require the knowledge of the value of at the transmitter [1, 2, 3].

The function update problem was considered in [2, 3] for DSS’s for updating one of the storage nodes with the help of the other nodes in the system. Note that each node in a DSS stores a linear function of the message. A node can become stale in such systems, for instance if the node goes offline while the message and the corresponding linear functions stored in the other nodes undergo an update. Once it is back online, the stale node connects to the other nodes in the distributed storage system to update its own linear function, and the stale data already stored in this node acts as side information. The authors of [2, 3] design both the code for distributed storage and the code for function update to minimize the amount of data downloaded by the stale node to update its contents. This is unlike the problem statement considered in [1] as well as this paper, where it is assumed that an arbitrary matrix A is given and a code for updating the function is to be designed.

The authors in [1] also consider a broadcast scenario where a codeword is broadcast to multiple nodes in order to update the (different) linear functions stored in each of the nodes. Problems related to updating linear functions have been considered in [4, 5, 6]. In [4], codes for updating linear functions are used in cache-aided networks to reduce the cost of multicasting a sequence of correlated data frames. The problem of efficiently storing multiple versions of a file in a DSS while ensuring a property called consistency is considered in [5, 6].

In the study of the point-to-point function update problem given in [2, 3, 1] the authors derive the following field-size independent lower bound on the codelength

 l≥min(m,2ϵ).

Note that, if , the lower bound on the codelength can be trivially achieved by transmitting . Hence, we will always assume that . The results in [1] show that codelength is achievable using maximally recoverable subcodes of , the subspace spanned by the rows of A, which are guaranteed to exist if the field size . Note that this requirement imposed on the field size can be large even for moderate values of and . The authors of [1] also consider the special case where the matrix A is striped, i.e.,

 A=Ia⊗C=⎡⎢ ⎢ ⎢ ⎢ ⎢⎣C0…00C…0⋮⋮⋱⋮00…C⎤⎥ ⎥ ⎥ ⎥ ⎥⎦

where is the identity matrix, and denotes the Kronecker product. Note that and . This structure frequently arises in distributed storage systems where the -length data is partitioned into subvectors , each of length , each subvector is encoded independently by multiplying with , and all the encoded vectors are stored in a single storage node, see Examples 1–3 of [1]. In [1, Section IV], a code is constructed for the case that achieves the codelength using an MDS code, which is guaranteed to exist if the field size . In Remark 4 of [1] the authors consider a modified system model for the function update problem which we show in Section V-A3 of this paper to be equivalent to the case where A is striped with the number of stripes . Construction 1 and Remark 4 of [1] provide a code construction for this modified system model, and hence for the case , that achieves codelength of over any field.

In this paper we provide a field-size aware characterization of the point-to-point function update problem. In particular, we provide bounds on the achievable codelength that take into account the effect of the field size and we provide constructions that trade-off the codelength for a smaller field size requirement. This is unlike the point-to-point results in [1] which provide constructions only for the case but assume that the field size is sufficiently large. To the best of our knowledge, no prior analysis of this problem as a function of the field size is available in the literature except [1] which assumes that the field size is large enough for a maximally recoverable code to exist.

We characterize the family of point-to-point function update problems where linear coding scheme is useful to save at least one transmission, i.e., is achievable (Theorem 3, Section III). This characterization is analyzed in terms of the covering radius of , the dual of the code , in Section III-B. We provide a lower bound (Theorem 4, Section IV) and an upper bound (Theorem 5, Section V) on optimal codelength based on linear error correcting codes. Similar to [1] we also provide code constructions when A is striped (Section V-A1,V-A2) but our focus is on the general case where and . For the case when we provide a construction (Section V-A1) which achieves the optimal codelength for the respective operating field size , for any prime power . For the special case this code construction achieves codelength and this matches the achieved codelength in Construction 2 of [1] for which also requires . Section V-A2 provides code constructions for using subspace codes and error correcting codes over field extensions. All these code constructions yield a trade-off between the chosen field size and achieved codelength where operating over a smaller field size results in a larger codelength than operating over a larger field size (for instance, see Example 3). When restricted to the special case our construction provides a valid coding scheme for the modified function update problem mentioned in [1, Remark 4] that matches codelength over any field reported in [1] (Section V-A3). The performance comparison of the constructed codes are discussed in Section V-A4. Finally, we show that the point-to-point function update problem is equivalent a functional index coding or a generalized index coding problem [7, 8, 9]. Given a point-to-point function update problem we construct a functional index coding problem (Algorithm 1, Section VI-B) such that a coding scheme is valid for the function update problem if and only if it is valid for the constructed functional index coding problem (Theorem 9, Section VI-B). This paper starts with describing the system model and providing relevant preliminary results in Section II.

Notation: Matrices and column vectors are denoted by bold uppercase and lowercase letters, respectively. For any positive integer , the symbol denotes the set . The Hamming weight of a vector is denoted as . The symbol denotes the finite field of size and denotes a column vector of elements over where is a prime power. The identity matrix is denoted as .

## Ii System Model and Preliminaries

We consider a noiseless communication scenario with single transmitter and single receiver. The transmitter knows a column vector of information symbols where each information symbol is an element over finite field . The receiver stores the coded message where () and rank(A) = . Now suppose the information symbol vector is updated to where is the update vector which is also a column vector of length over with , where denotes the Hamming weight of a vector. The objective is to generate a codeword with codelength as small as possible such that the receiver can update its content to using the transmitted codeword and the older version of its content . We assume the transmitter doesn’t know about original information symbol vector or update vector but only knows the updated information symbol vector . The problem of designing coding scheme to update the coded data available at the receiver to with will be called as function update problem.

###### Definition 1.

A valid encoding function of codelength for the function update problem over the field is a function

 E:Fnq ⟶ Flq

such that there exists a decoding function satisfying the following property: for every and with .

The objective of the code construction is to design a pair of encoding and decoding functions that minimizes the codelength and to calculate the optimal codelength over which is the minimum codelength among all valid coding schemes.

A coding scheme is said to be linear if the encoding function is an

-linear transformation. For a linear coding scheme, the codeword

, where . The matrix is the encoder matrix of the linear coding scheme. The minimum codelength among all valid linear coding schemes for the function update problem over the field will be denoted as .

The trivial coding scheme that transmits the updated coded information symbols i.e., is a valid coding scheme with codelength since the receiver can directly update its content using . We refer to this trivial coding scheme as naive scheme where . Thus, we have the following trivial upper bound on the optimum linear codelength

 lq,opt≤m. (1)

In [1] the authors provided a necessary and sufficient condition for a matrix to be a valid encoder matrix for function update problem. In Theorem 2 of [1] the proof is given only for necessary condition for a matrix to be a valid encoder matrix for function update problem. For the sake of completeness here we first prove that the criterion 1 in [1, Theorem 2] is a necessary and sufficient condition for a matrix to be a valid encoder matrix for function update problem and then state the relevant results which will be helpful to derive other results of this paper. Let and denote the linear codes generated by the rows of A and respectively. Also let and let be a generator matrix of .

###### Theorem 1 (Theorem 2, [1]).

A matrix is a valid encoder matrix for the function update problem if and only if for any with and .

###### Proof.

A matrix is a valid encoder matrix for the function update problem if and only if the receiver can uniquely determine from the received codeword and the side information . Hence for two pairs of information symbol vectors and update vectors and such that the coded information symbol vectors available at the receiver are identical i.e., but updated coded information symbol vectors are distinct i.e., then the transmitted codeword must be distinct from to distinguish the two different updated coded information symbol vectors. Equivalently, the condition should hold for every choice of with satisfying and . Therefore is a valid encoder matrix if and only if

 H(x−x′)≠H(e′−e)

for all such that and . Now denoting and we have

 Hz≠Hy (2)

for all and such that and . Now reformulating the condition given in (2) we obtain for all that satisfy , and . Therefore is a valid encoder matrix if and only if for all and if and then . Hence is a valid encoder matrix if and only if for all with if then . Now using the fact that we deduce that is a valid encoder matrix if and only if for all with such that also satisfies . Hence the statement of the theorem follows. ∎

###### Lemma 1 (Remark 2, [1]).

Let be a valid encoder matrix for the function update problem. Let be a generator matrix of the code . Then is also a valid encoder matrix for the function update problem.

If we consider a valid encoder matrix such that , then we can find another valid encoder matrix as the generator matrix of the code . Since is a subcode of , we have . Therefore the encoder matrix has sub-optimal codelength. So from now we only consider encoder matrices such that . Since we assume we can write for some matrix .

Now using we restate Theorem 1 as follows. A matrix such that is a valid encoder matrix for the function update problem if and only if for any with and satisfies . We define the collection as the set of all vectors with such that i.e.,

 I(A,ϵ)={y∈Fnq | Ay≠0, 0
###### Theorem 2.

A matrix for some matrix is a valid encoder matrix for the function update problem if and only if

 Hy≠0,   ∀y∈I(A,ϵ).

Now we define the collection as the set of all non-zero linear combinations of or fewer columns of A over i.e.,

 IFU(A,ϵ)={Ay | 0

Note that since .

###### Corollary 1.

is a valid encoder matrix for the function update problem if and only if

 Sz≠0,   ∀z∈IFU(A,ϵ).

## Iii Necessary and Sufficient Condition for lq,opt<m

In this section we will characterize the family of point-to-point function update problems where linear coding is useful to save at least one transmission compared to the naive scheme i.e., . First we will derive some preliminary results which will be helpful to derive the main result of this section.

###### Lemma 2.

The collection is closed under non-zero scalar multiplication.

###### Proof.

Suppose . There exists a with such that . For any , , where . Now as , it follows that . Again as and . Therefore for any , . Hence the lemma holds. ∎

### Iii-a A coding scheme for a family of (A,ϵ) function update problems

Consider any function update problem where there exists a non-zero such that . Let be the subspace of generated by . Therefore dim. Note that dim. Let be a generator matrix of the code . The matrix S is a parity check matrix of the code .

###### Lemma 3.

The matrix S satisfies for all .

###### Proof.

Proof by contradiction. Let there exist a such that . This implies that . Therefore there exists an such that . Now as , exists and hence . Now as and is closed under non-zero scalar multiplication (using Lemma 3), which is a contradiction. Hence the lemma holds. ∎

Now using Corollary 1, we obtain a valid encoder matrix for the function update problem over as with codelength , whenever there exists a non-zero vector in . We do not claim that this coding scheme yields the optimal codelength .

###### Example 1.

Consider the function update problem over binary field where , , and the matrix is given by

 A=⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣1101001100100100100100110010111110110011⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦.

Note that rank over . The non-zero vector satisfies . The parity check matrix of the code , generated by is given by

 S=⎡⎢ ⎢ ⎢⎣10011011000001111110⎤⎥ ⎥ ⎥⎦.

Therefore we obtain a valid encoder matrix with codelength for the function update problem as

 H=SA=⎡⎢ ⎢ ⎢⎣01001111101101111001110001001011⎤⎥ ⎥ ⎥⎦.

Now we derive a necessary and sufficient condition for any function update problem to save at least one transmission using linear coding scheme compared to the naive scheme.

###### Theorem 3.

For an function update problem, if and only if .

###### Proof.

To prove the theorem we first show that for any function update problem if then . Next we show that if then .
Proof of first part i.e., if then :

Let be an optimal encoder matrix with . Then there exists a matrix such that . From Corollary 1 we obtain for all . Since contains all non-zero vectors from , the columns of S are linearly independent. Hence . Again from (1), we have . Hence .
Proof of second part i.e., if then :

If then there exists a non-zero vector such that . Therefore using the technique described in Section III-A we can construct a valid encoder matrix such that we save one transmission compared to the naive scheme, i.e., . Hence the lemma holds. ∎

Now we provide a sufficient condition on the field size to save at least one transmission compared to the naive scheme for any function update problem.

###### Corollary 2.

For any with rank where ,

if

.

###### Proof.

If then

 qm−2ϵ ≥(n2ϵ) or,  qmq2ϵ ≥(n2ϵ).

Using the fact that if then , we have

 qm−1q2ϵ−1 >qmq2ϵ   (since qm>q2ϵ) or,  qm−1q2ϵ−1 >(n2ϵ) or,  qm−1 >(n2ϵ)(q2ϵ−1).

Now for any with rank, the number of distinct non-zero linear combinations of or fewer columns of A is at the most . Therefore . Hence . Now using Theorem 3 we have . ∎

### Iii-B Relation with covering radius

The covering radius of an linear code over , denoted by , is defined as the smallest integer such that the spheres of radius centered at each codeword of cover the whole space . We can determine covering radius of a linear code in terms of the cosets of the code. For any vector , the set is called a coset of the code and in any coset, a vector with minimum Hamming weight is called a coset leader. The covering radius of the code is the largest among the Hamming weight of all the coset leaders. Upon denoting as a parity check matrix of , is the syndrome of the vector . Two vectors have the same syndrome if and only if they belong to the same coset of . Hence there is an one-to-one correspondence between syndromes and cosets [10].

For the function update problem let be the linear code generated by A. Hence A is a parity check matrix of the code which is the dual code of . Now considering a vector , can be expressed as where with . Therefore the vector denotes the syndrome of a vector with that belongs to some coset of . Note that any vector that belongs to is non-zero, hence can not be the syndrome of the codewords of . Note that is the syndrome of the coset leader of the coset . Since is a vector that belongs to the coset and , the Hamming weight of the coset leader of the coset is at the most .

###### Corollary 3.

For an function update problem, if and only if .

###### Proof.

From Theorem 3 we have if and only if . Hence to prove the corollary we prove that for any function update problem if and only if .
Proof of if : Since the collection contains all non-zero vectors over , each non-zero vector is the syndrome of some vector with that belongs to some coset of . Since there exists a one-to-one correspondence between the syndromes and cosets, for each vector there exists a coset of that contains a vector with . Hence the coset leader of each coset has Hamming weight at the most . Therefore the largest Hamming weight of the coset leaders among all cosets of is at the most . Hence .
Proof of if : Since , the largest Hamming weight of the coset leaders among all cosets of is at the most . Since there exists a one-to-one correspondence between the syndromes and cosets, each syndrome can be expressed as for some coset leader satisfies . We know that the syndromes of a particular linear code covers the whole space. Hence any vector can be expressed as for some with . Since consists only non-zero vectors that satisfies the above property, .

Hence if and only if . ∎

###### Example 2.

In this example we calculate the minimum number of rows of such that is guaranteed for , and . Now if and only if . From Table I of [11] we observe that for any binary code of length and dimension up to , covering radius is at least . Thus dim implies . Hence and . Therefore for any matrix with rank we can save one transmission compared to the naive scheme. One such example of A is given in Example 1. ∎

## Iv Lower Bound on Optimal Codelength

In this section we derive a lower bound on the optimal codelength over . First we derive two preliminary lemmas which will help to derive the lower bound.

###### Lemma 4.

For any

function update problem and for any invertible matrix

, .

###### Proof.

To prove the lemma we first show that and then .
Proof for : Suppose . Then from (3) we have . Now left multiplying both side by K we obtain since K is invertible. Hence .
Proof for : Suppose . Then from (3) we have . Since K is invertible, exists. Now left multiplying both side by we obtain . Hence .

Hence the lemma holds. ∎

For any function update problem with rank(A)=. Hence A contains linearly independent columns. Now consider a matrix which contains linearly independent columns of A. Note that is an full rank matrix and hence invertible. Denote and . From Lemma 4 we observe that and are equivalent function update problems and any matrix is a valid encoder matrix of function update problem if and only if is a valid encoder matrix of function update problem. Hence we conclude that the linear code generated by the rows of is a subcode of the linear code generated by the rows of i.e., . Hence there exists a matrix such that . Now using the equivalence between and function update problems and using Corollary 1 we say that is a valid encoder matrix of the function update problem if and only if for all .

Let be the set of all non-zero vectors in of Hamming weight at the most .

###### Lemma 5.

For any function update problem

.

###### Proof.

For an function update problem, where and consists of linearly independent columns of A. Note that the sub-matrix of that contains the corresponding columns forms an identity matrix. Now if we consider any non-zero linear combination of of fewer columns of this sub-matrix we obtain all non-zero vectors over with Hamming weight at the most . Hence . The last equality holds due to Lemma 4. ∎

Let be the maximum dimension among all linear codes over with blocklength and minimum distance .

###### Theorem 4.

The optimal codelength of the function update problem over satisfies

.

###### Proof.

Let be an optimal encoder matrix of function update problem with codelength . Then there exists a matrix such that . Now using Corollary 1 we have for all . Since , it follows that for all . Therefore any set of columns of S are linearly independent. Hence S is a parity check matrix of a linear code of block length and minimum distance at least . Thus the dimension of this code satisfies . Then . ∎

Theorem 4 provides a lower bound that is aware of the field size . This is tighter than the bound given in [2, 3, 1] since from Singleton bound we know that , and this combined with Theorem 4 yields . Hence, irrespective of the matrix A, a necessary condition for is that an MDS code over must exist.

## V Code constructions

In this section we first derive an upper bound on the optimal codelength over and then provide code constructions for function update problem when A is in form given by (4). Define .

###### Theorem 5.

The optimal codelength of the function update problem over satisfies

.

###### Proof.

From Corollary 1 we have that a matrix for some matrix , is a valid encoder matrix if and only if . To satisfy this condition it is sufficient that any set of columns of S are linearly independent. Now consider S as a parity check matrix of the largest linear code with blocklength and minimum distance . The resulting codelength . Hence the upper bound on the optimal codelength holds. ∎

### V-a Code constructions for striped data

In this section we provide linear code construction of an function update problem where follows the structure given by

 AS=⎡⎢ ⎢ ⎢ ⎢ ⎢⎣C0…00C…0⋮⋮⋱⋮00…C⎤⎥ ⎥ ⎥ ⎥ ⎥⎦ (4)

where and is a matrix over whose all elements are . Let be the number of repetitions of in the matrix . Hence we write and . First we consider the family of function update problems where and show that for this case the lower bound on optimal codelength given in Theorem 4 and the upper bound on optimal codelength given in Theorem 5 exactly matches with each other. Hence we characterize the optimal codelength for this family of function update problems. Our code construction is based on an appropriately chosen linear error correcting code. Note that in Section IV of [1] the authors provided a linear code construction based on maximally recoverable subcodes (MRSC) which requires field size and uses an MDS code. In comparison our code construction is suitable for any field size.

#### V-A1 Code Constructions for the family of (AS,ϵ) function update problems with t=1

In this sub-section we first calculate the optimal codelength for such family of function update problems and then provide a code construction based on an appropriately chosen linear error correcting code.

###### Theorem 6.

For the family of function update problems with the optimal codelength over


text:
# A line segment with endpoints at (5 , -9 ) and (2, -2 ) is rotated clockwise by (3 pi)/2. What are the new endpoints of the line segment?

Jun 22, 2016

(5 ,-9) → (9 ,5) and (2 ,-2) → (2 ,2)

#### Explanation:

I am assuming a rotation about the origin.

Under a rotation about the origin of $\frac{3 \pi}{2}$

A point (x ,y) → (-y ,x)

Hence (5 ,-9) → (9 ,5) and (2 ,-2) → (2 ,2)


text:
# Achromatic Aberration

Combining two lenses can overcome the chromatic aberration in them. Therefore, when two lenses are combined in such a manner that the combination is free from chromatic aberration, then such a combination is called achromat or achromatic aberration combination of lenses.

Consider two thin lenses $L$ and $L’$ of materials of dispersive power $ω$ and $ω’$ respectively are placed in contact with each other as shown in figure.

Let $(μ_v, μ, μ_r)$ and $(f_v, f, f_r)$ be the refractive indices and focal lengths of the material of the lens $L$ for violet, mean and red light respectively. Let $R_1$ and $R_2$ be radii of curvature of the two surfaces of lens $L$.

Let $(μ_v’, μ’, μ_r’)$ and $(f_v’, f’, f_r’)$ be the refractive indices and focal lengths of the material of the lens $L’$ for violet, mean and red light respectively. Let $R_1’$ and $R_2’$ be radii of curvature of the two surfaces of lens $L’$.

For lens $L$, the focal length of the lens for mean light is given by, $\frac{1}{f}=(μ-1)\left(\frac{1}{R_1}+\frac{1}{R_2}\right)$ $\left(\frac{1}{R_1}+\frac{1}{R_2}\right)=\frac{1}{f(μ-1)}$

The focal length of the lens $L$ for violet light is given by, $\frac{1}{f_v}=(μ_v-1)\left(\frac{1}{R_1}+\frac{1}{R_2}\right)$

Substituting the value of $\left(\frac{1}{R_1}+\frac{1}{R_2}\right)$, $\frac{1}{f_v}=\frac{μ_v-1}{f(μ-1)}$

Similarly, focal length of lens $L’$ for violet light is given by, $\frac{1}{f_v’}=\frac{μ_v’-1}{f’(μ’-1)}$

If $F_v$ is the focal length of the combination of the lenses for the violet light, then, $\frac{1}{F_v}=\frac{1}{f_v}+\frac{1}{f_v’}$ $\frac{1}{F_v}=\frac{μ_v-1}{f(μ-1)}+ \frac{μ_v’-1}{f’(μ’-1)}$

Similarly, the focal length of the combination of the lenses for the red light, then, $\frac{1}{F_r}=\frac{μ_r-1}{f(μ-1)}+ \frac{μ_r’-1}{f’(μ’-1)}$

### Condition for Achromatic Aberration

If the combination is achromatic, the violet and red rays will come to focus at a single point i.e.

$F_v=F_r$

$\frac{1}{F_v}=\frac{1}{F_r}$

$\frac{μ_v-1}{f(μ-1)}+ \frac{μ_v’-1}{f’(μ’-1)}= \frac{μ_r-1}{f(μ-1)}+ \frac{μ_r’-1}{f’(μ’-1)}$

$\left[\frac{μ_v-1}{f(μ-1)}- \frac{μ_r-1}{f(μ-1)}\right]+\left[\frac{μ_v’-1}{f’(μ’-1)}- \frac{μ_r’-1}{f’(μ’-1)}\right]=0$

$\left[\frac{(μ_v-1)-(μ_r-1)}{f(μ-1)}\right]+\left[\frac{( μ_v’-1)-(μ_r’-1)}{f’(μ’-1)}\right]=0$

$\left[\frac{μ_v-μ_r}{f(μ-1)}\right]+\left[\frac{μ_v’-μ_r’}{f’(μ’-1)}\right]=0$

$\text{We have, }ω=\frac{μ_v-μ_r}{μ-1} \text{ and, }ω’=\frac{μ_v’-μ_r’}{μ’-1}$

$\text{Therefore, }\frac{ω}{f}+\frac{ω’}{f’}=0$

This is the condition for achromatism for two thin lenses in contact.

Since the dispersive power is always positive, $ω$ and $ω’$ are positive. Therefore, $f$ and $f’$ should be of opposite signs i.e. if one lens is convex then the other should be concave.

The two thin lenses cannot be of same material. If the two lenses are of same material then $ω=ω’$.

$\therefore\frac{ω}{f}+\frac{ω}{f’}=0$ $\frac{1}{f}+\frac{1}{f’}=0$ $\text{Also, }\frac{1}{f}+\frac{1}{f’}=\frac{1}{F}$ Where, $F$ is the focal length of the combination of two thin lenses in contact.

$\text{Thus, }\frac{1}{F}=0$ $F=∞$ Therefore, if the lenses are of same material, then a beam of light will neither converge nor diverge on passing through the combination. Hence, two lenses cannot be of same material.

[Also See: Dispersion]


text:
# Infinite line charge (without Gauß's law)

1. Sep 20, 2008

### Phoboid

Hi!
I would like to find the electric field of an infinite line charge without using Gauß's law.
I already simply integrated over the line charge, which gave me the correct result.
However, I would like to try yet another approach: the potential equation, which states that:

$$\Delta \phi = \frac{\rho}{\epsilon_0}$$,
for the electric potential.
For the infinite line charge, we can use the Laplacian for cylindrical coordinates, which is
$$\Delta= {1 \over r} {\partial \over \partial r} \left( r {\partial \over \partial r} \right) + {1 \over r^2} {\partial^2 \over \partial \theta^2} + {\partial^2 \over \partial z^2 }$$.

Because the situation is symmetric, all derivatives with respect to $$\theta, z$$ vanish.
The charge density must also be 0 for r>0.
The equation I have to solve thus looks like:
$${1 \over r} {\partial \over \partial r} \left( r {\partial \phi \over \partial r} \right) = 0$$.

By integrating twice, I get
$$\phi = \alpha \ln(r) + \beta$$
which has the correct form I want. I then chose $$\phi(1) = 0 \Rightarrow \beta = 0$$

My problem comes now: How do I get $$\alpha$$?

2. Sep 20, 2008

### CompuChip

I don't quite follow your calculation. If you have an infinite line charge, then why would you use cylindrical coordinates? Isn't it much easier to just put the charge along one of the axes and use Cartesian coordinates?

[OK, your point probably is, that this would come down to just integrating over the line charge in the end, because first you integrate rho twice to get phi, and then differentiate that to get E]

Also, I don't really see why you impose the boundary conditions you do. You are putting the line charge along the x-axis (the z-axis seems more convenient, but then again you might as well do it in Cartesian coordinates)? But then why is the charge density zero for r > 0 and why would you want to choose the potential zero at r = 1 ?

3. Sep 20, 2008

### Phoboid

Thanks for your reply. You're right, I should have been more clear in my explanations:
I'm using cylindrical coordinates because the potential must be cylindrically symmetric, I thought it was kinda the natural choice.
In my calculation, I put the charge along the z axis, therefore $$r^2 = x^2 + y^2$$ is the (squared) distance from that axis.

The charge is only on the z axis, and with my choice of r, the density must be 0 everywhere else.
I chose $$\phi(1) = 0$$ so $$\beta$$ would vanish, just for aesthetical reasons ;).
Of course, in the end, I want to get the actual electric field using
$$\mathbf E = -\nabla \phi$$

I hope this has cleared up the situation a bit.
Thanks for any help!

Last edited: Sep 20, 2008
4. Sep 20, 2008

### atyy

Specify the charge density, solve for the potential in the charge density and match solutions at the boundary. Probably alpha is more important than beta, since the potential is unique only up to an additive constant?

5. Sep 20, 2008

### Phoboid

As what I have here is a line charge, there is no "inside" that I could solve the potential equation for.
I could try to first solve everything for a infinitely long cylinder with radius r and then take the limit as r tends to 0.

6. Sep 21, 2008

### Irid

Getting $$\alpha$$ here is a little messy business. In essence, it's just applying the boundary conditions, so you should integrate both sides of Gauss's law:

$$\int \alpha \nabla^2 \ln r\, da = \int \frac{\rho}{\epsilon_0}\, da = \frac{\lambda}{\epsilon_0}$$

Now the first integral is a fishy one and you must be really careful about it. What I guess is that it can be solved by means of a 2D version of Gauss's theorem:

$$\int \nabla^2 \ln(r)\, da = \int \boldsymbol{\nabla \cdot} (\nabla \ln(r))\, da = \int \nabla \ln(r) \, dl = \int \frac{1}{r}\, rd\phi = 2\pi$$

So you would have

$$\alpha = \frac{\lambda}{2\pi \epsilon_0}$$

The dimensions are alright, just check the 2pi factor using the usual methods.

7. Sep 21, 2008


text:
# Find the energy (in kJ) of a wave with a wavelength of 507 nm.

## Question:

Find the energy (in kJ) of a wave with a wavelength of 507 nm.

## Energy's Formula and Units:

The formula for the required energy of wave measured in joules for this problem in terms of the wavelength of the wave {eq}\lambda {/eq} is shown below:

{eq}\displaystyle E=\frac{hc}{\lambda} {/eq}, where,

• "h" is Planck's constant and it is equal to {eq}6.63\times 10^{-34}\ J\cdot s {/eq}.
• "c" is the value of the speed of the light and its standard value is {eq}3\times 10^8\ m/s {/eq}.

The relation between the units of the energy of the wave is:

{eq}\rm 1\ joule=\frac{1}{1000}\ kilojoules {/eq}

The given value is:

• The value of the wavelength of the wave is {eq}\lambda =507\ nm {/eq}.

The value of the above wavelength in meters is:

{eq}\begin{align*} \displaystyle \lambda& =\rm 507\ nm\times \frac{10^{-9}\ m}{1\ nm}\\ & =\displaystyle \rm 507\times 10^{-9}\ m\\ \end{align*} {/eq}

Substituting all the above values with the standard values in the formula of the energy and simplifying it, we get:

{eq}\begin{align*} \displaystyle E&=\frac{6.63\times 10^{-34}(3\times 10^8)}{507\times 10^{-9}}\\ \displaystyle E&=\frac{19.89\times 10^{-26}}{507\times 10^{-9}}\\ \displaystyle E&=3.92\times 10^{-19}\ J\\ \end{align*} {/eq}

Converting the unit of the above value in kilojoule, we get:

{eq}\begin{align*} \displaystyle E&=3.92\times 10^{-19}\ J\times \frac{1\ kJ}{1000\ J}\\ &=3.92\times 10^{-19}\times 10^{-3}\ kJ\\ &=\boxed{\rm 3.92\times 10^{-22}\ kJ}\\ \end{align*} {/eq}


text:
# Black and White

OK guys, I think this is my best puzzle yet. Hope you enjoy it, the solution is neat and simple.

A boy draws 2015 unit squares on a piece of paper, all oriented the same way. The squares can overlap. Then he colors the resulting picture in black and white chess-wise, such that any area belonging to an even number of squares is painted white and any area belonging to an odd number of squares is painted black.

Prove that there is at least one square unit of black on the paper when he is finished.

• Man this boy sure knows how to have a good time. – Going hamateur Jul 21 '15 at 18:26
• My apologies, I misinterpreted the words – CodeNewbie Jul 21 '15 at 18:47
• "Just do it!" proof time! :D – COTO Jul 21 '15 at 22:10

Let's think of the problem as taking XOR's (symmetric differences) of the square areas, with black as 1 and white as 0. The black area is the XOR of all the squares.

Imagine doing this all on graph paper whose cells are sized and oriented like the squares. Take the resulting figure, cut up the occupied cells, and stack them on top of each other without rotating. Now, take the XOR of that stack.

Note that any square on the graph paper gets cut up and rearranged to make exactly the full unit cell. So, the XOR of the stack is the XOR of 2015 fully black squares, which is all black, since 2015 is odd. Then, since each black point in the XOR requires at least one black point the contribute, the total area of black in the stack must be at least 1.

Needlessly formally:

We are interested in the group $G$ of (well-behaved) finite-area subsets of the plane under symmetric difference (XOR). We quotient out the plane by integer translations to get $(\mathbb R \times \mathbb R) / (\mathbb Z \times \mathbb Z)$, which induces a homomorphism $\phi$ from $G$ to the corresponding group $G'$ on the unit square.

We have $2015$ single-square elements $x_1, ..., x_{2015}$ of $G$ and are interested in their sum $x$. As single-square elements, they all map to the same full-square element $\phi(x_i) = s$ in $G'$, so $\phi(x) = s + \cdots + s$ summed $2015$ times. Since $G'$ has order $2$, this is simply $s$. But the homomorphism $\phi$ cannot increase the size of the subset, so

$$\mathrm{Area}(x) \geq \mathrm{Area}(\phi(x)) = \mathrm{Area}(s) =1$$

• Beautiful solution, even prettier than mine. Good job! – Puzzle Prime Jul 21 '15 at 23:01
• @ArturKirkoryan How did you solve it? – xnor Jul 21 '15 at 23:07
• First proved it by induction for unit segments on a line. Then projected all squares on a line parallel to one of their sides and applied twice the 1-dimensional case. – Puzzle Prime Jul 21 '15 at 23:13
• I don't follow how this reasoning preserves the colouring. Suppose we follow the top procedure with just two non-overlapping squares. The graph paper happens to have two full squares occupied, so they are cut and stacked. Taking the xor would give white everywhere, whereas the boy would have coloured both squares black. What am I missing from your explanation? – Lawrence Jul 21 '15 at 23:49
• @Lawrence All of that is right. If you had three squares though, the xor of the stack would be black everywhere, so there must be at least 1 black area. – xnor Jul 22 '15 at 0:18

In order to minimize the area shaded black, we want as many squares possible to perfectly overlap in even numbers. For example, take two squares. Separated, they are both single layers, and therefore provide $2$ $units^2$ of black paint. So we overlap these two. If we let the overlapping area be $A$, we then have $(1-A) + (1-A) = 2(1-A) units^2$ of black area. It is quite easy to see that to minimize the amount of area colored black we want $A=1$; the squares perfectly overlap.

So then we "pair" each square up with one another in order to minimize the amount of area being colored black. In this case we have 2015 squares, forming 1007 pairs with one square left over. The 1007 pairs, no matter how they are distributed, will add 0 black area to the total. So then we are left with the problem of where to place the remaining square in order to minimize the area colored black. Notice that since we formed pairs, our remaining square will be placed in an area that is shared by 0, 2, 4, etc, squares already. Thus no matter where we place our last square, all of its area will be shared by an odd number of squares. So our minimal area being colored black is the area of our one square: $1$ $unit^2$.

Alternative proof:

For $N$ squares, we can clearly see that if there is no overlap, then we will need to fill in a maximal area of $N$ units. So in this setup, we pick one square to "slide" around. If while sliding it around we encounter another square(s), then two things can happen: the total black area remains the same, the total black area decreases. In order for it to remain the same, the square would need to enter a region that is already shared by an even number of squares. If an odd number of squares share the region, then it's like the situation in the solution above where $A$ (the shared area) is now increasing from 0. As $A$ increases, the amount being colored black will decrease.

Thus we can continuously pick and slide squares around on the sheet. If we place the square into a region already shared by other squares, then we know that the total black area is either the same or less. Notice that by sliding squares, we can achieve any possible configuration of $N$ squares on the sheet of paper. Now notice the case where we slide all the squares perfectly onto each other. As $N$ is odd in this case, we know that the area of this configuration is $1$. More importantly, we know from our previous observations, that if we were to alter this configuration by sliding a square away from other squares then the black area will either stay the same, or increase. Thus any configuration of squares will have a minimal area of $1$.

• What if we have several squares at once overlapping with each other? The black areas can look very intricate. – Puzzle Prime Jul 21 '15 at 19:04
• @ArturKirkoryan, it sounds like this solution takes that into consideration: "...to minimize the amount of area colored black we want $A=1$; the squares perfectly overlap." – GentlePurpleRain Jul 21 '15 at 19:13
• @GentlePurpleRain, yeah, but this A=1 applies only if we are trying to minimize the black area resulting from 2 squares alone. Then they should really completely overlap, so that both will vanish. However, I don't think this implies that all of the squares except for one should overlap in pairs. – Puzzle Prime Jul 21 '15 at 19:16
• @ArturKirkoryan I was using the overlapping of two squares to show a way to achieve a minimal area of black. I added another proof that approaches it from another way. – dzastergamer Jul 21 '15 at 19:36
• @dzastergames, after you have placed several squares, overlapping each other, the black areas resulting around can have various shapes. This way when you take some isolated square and start placing it around this construction, it will be hard to analyze what happens exactly. I think you have good intuition, but will need some mathematical approaches to make things rigorous. – Puzzle Prime Jul 21 '15 at 20:33

I'm sure I'm misunderstanding something. But here we go:

http://i.imgur.com/bVaysoT.png

Overlap 2013 of them on top of each other and have the other two slightly offset.

• Nice picture:) The total black area becomes more than 1, this is what we have to prove. – Puzzle Prime Jul 22 '15 at 2:10
• Oh I see, I was misread one square unit. And now it's fun again, thanks. Edit: I only made an answer because I was under the impression I couldn't write comments. – millsy Jul 22 '15 at 2:14


text:
Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

# ifft2

2-D inverse fast Fourier transform

## Syntax

X = ifft2(Y)
X = ifft2(Y,m,n)
X = ifft2(___,symflag)

## Description

example

X = ifft2(Y) returns the two-dimensional discrete inverse Fourier transform of a matrix using a fast Fourier transform algorithm. If Y is a multidimensional array, then ifft2 takes the 2-D inverse transform of each dimension higher than 2. The output X is the same size as Y.

example

X = ifft2(Y,m,n) truncates Y or pads Y with trailing zeros to form an m-by-n matrix before computing the inverse transform. X is also m-by-n. If Y is a multidimensional array, then ifft2 shapes the first two dimensions of Y according to m and n.

example

X = ifft2(___,symflag) specifies the symmetry of Y. For example, ifft2(Y,'symmetric') treats Y as conjugate symmetric.

## Examples

collapse all

You can use the ifft2 function to convert 2-D signals sampled in frequency to signals sampled in time or space. The ifft2 function also allows you to control the size of the transform.

Create a 3-by-3 matrix and compute its Fourier transform.

X = magic(3)
X = 3×3

8     1     6
3     5     7
4     9     2

Y = fft2(X)
Y = 3×3 complex

45.0000 + 0.0000i   0.0000 + 0.0000i   0.0000 + 0.0000i
0.0000 + 0.0000i  13.5000 + 7.7942i   0.0000 - 5.1962i
0.0000 - 0.0000i   0.0000 + 5.1962i  13.5000 - 7.7942i

Take the inverse transform of Y, which is the same as the original matrix X, up to round-off error.

ifft2(Y)
ans = 3×3

8.0000    1.0000    6.0000
3.0000    5.0000    7.0000
4.0000    9.0000    2.0000

Pad both dimensions of Y with trailing zeros so that the transform has size 8-by-8.

Z = ifft2(Y,8,8);
size(Z)
ans = 1×2

8     8

For nearly conjugate symmetric matrices, you can compute the inverse Fourier transform faster by specifying the 'symmetric' option, which also ensures that the output is real.

Compute the 2-D inverse Fourier transform of a nearly conjugate symmetric matrix.

Y = [3+1e-15*i 5;
5 3];
X = ifft2(Y,'symmetric')
X = 2×2

4     0
0    -1

## Input Arguments

collapse all

Input array, specified as a matrix or a multidimensional array. If Y is of type single, then ifft2 natively computes in single precision, and X is also of type single. Otherwise, X is returned as type double.

Data Types: double | single | int8 | int16 | int32 | uint8 | uint16 | uint32 | logical
Complex Number Support: Yes

Number of inverse transform rows, specified as a positive integer scalar.

Data Types: double | single | int8 | int16 | int32 | uint8 | uint16 | uint32 | logical

Number of inverse transform columns, specified as a positive integer scalar.

Data Types: double | single | int8 | int16 | int32 | uint8 | uint16 | uint32 | logical

Symmetry type, specified as 'nonsymmetric' or 'symmetric'. When Y is not exactly conjugate symmetric due to round-off error, ifft2(Y,'symmetric') treats Y as if it were conjugate symmetric. For more information on conjugate symmetry, see Algorithms.

collapse all

### 2-D Inverse Fourier Transform

This formula defines the discrete inverse Fourier transform X of an m-by-n matrix Y:

${X}_{p,q}=\frac{1}{m}\sum _{j=1}^{m}\frac{1}{n}\sum _{k=1}^{n}{\omega }_{m}^{\left(j-1\right)\left(p-1\right)}{\omega }_{n}^{\left(k-1\right)\left(q-1\right)}{Y}_{j,k}$

ωm and ωn are complex roots of unity:

$\begin{array}{l}{\omega }_{m}={e}^{2\pi i/m}\\ {\omega }_{n}={e}^{2\pi i/n}\end{array}$

i is the imaginary unit. p runs from 1 to m and q runs from 1 to n.

## Algorithms

• The ifft2 function tests whether the vectors in a matrix Y are conjugate symmetric in both dimensions. A vector v is conjugate symmetric when the ith element satisfies v(i) = conj(v([1,end:-1:2])). If the vectors in Y are conjugate symmetric in both dimensions, then the inverse transform computation is faster and the output is real.