text:
## Cryptology ePrint Archive: Report 2016/1153

Attacks against search Poly-LWE

Momonari Kudo

Abstract: The Ring-LWE (RLWE) problem is expected to be a computationally-hard problem even with quantum algorithms. The Poly-LWE (PLWE) problem is closely related to the RLWE problem, and in practice a security base for various recently-proposed cryptosystems. In 2014, Eisentraeger et al. proposed attacks against the decision-variant of the PLWE problem (and in 2015, Elias et al. precisely described and extended their attacks to be applied for that of the RLWE problem). Their attacks against the decision-PLWE problem succeed with sufficiently high probability in polynomial time under certain assumptions, one of which is that the defining polynomial of the PLWE instance splits completely over the ground field. In this paper, we present polynomial-time attacks against the search-variant of the PLWE problem. Our attacks are viewed as search-case variants of the previous attacks, but can deal with more general cases where the defining polynomial of the PLWE problem does not split completely over the ground field.

Category / Keywords: Ring-LWE, Poly-LWE, finite field

Date: received 15 Dec 2016, last revised 20 Dec 2016

Contact author: m-kudo at math kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2016/1153

[ Cryptology ePrint archive ]


text:
# Probability, Ergodic Theory, Mathematical Physics Seminar

## Exact Asymptotic Speed of a Traveling Wave with Large Noise

Carl Mueller, Rochester

Friday, April 26th, 2019
3:00 PM - 4:00 PM
Hylan 1106A

This is joint work with Leonid Mytnik and Lenya Ryzhik.

Traveling waves are a widespread phenomenon in physical systems. The Fisher-Kolmogorov-Petrovskii-Piscuinov (FKPP) equation is one of the simplest equations exhibiting traveling waves. Since physical systems often experience random disturbances, there is interest in the study of traveling waves in the presence of noise. We study solutions $u_t(x)$ to the following stochastic FKPP equation:

where $\dot{W}(t,x)$ is two-parameter white noise. Here $x\in\mathbf{R}$, and we assume that $u_0(x)=\mathbf{1}(x\leq0)$.

One can define the right hand edge $R(u_t)$ of the solution, and we consider the speed

There has already been work on the asymptotics of $V(\sigma)$ for $\sigma$ near 0. For large $\sigma$, Conlon and Doering gave the lower bound

We give a corresponding upper bound,

which shows that $\lim_{\sigma\to\infty}\sigma^2V(\sigma)=2$.

Event contact: arjun dot krishnan at rochester dot edu

format: plain


text:
## Appendix to Lecture 13

Analyzing Example 13.6 and Example 13.7. We claim that eigenvalues are monotone functions of $\alpha$, $\beta$.

To prove it we need without proof to accept variational description of eigenvalues of self-adjoint operators bounded from below (very general theory) which in this case reads as:

Theorem. Consider quadratic forms $$Q (u)= \int _0^l |u'|^2\,dx + \alpha |u(0)|^2 + \beta |u(l)|^2$$ and $$P (u)= \int _0^l |u|^2\,dx .$$ Then there are at least $N$ eigenvalues which are less than $\lambda$ if and only iff there is a subspace $\mathsf{K}$ of dimension $N$ on which quadratic form $$Q_\lambda (u)= Q(u)- \lambda P(u)$$ is negative definite (i.e. $Q_\lambda (u)<0$ for all $u\in \mathsf{K}$, $u\ne 0$).

Note that $Q(u)$ is montone non-decreasing function of $\alpha,\beta$. Therefore $N(\lambda)$ (the exact number of e.v. which are less than $\lambda$) is montone non-increasing function of $\alpha,\beta$ and therefore $\lambda_N$ is montone non-decreasing function of $\alpha,\beta$.


text:
# MRI K-space to image: why track frequencies in two dimensions?

While trying to better understand how an MRI goes from k-space to an image, I came across this wonderful website that explains how you would represent an image as a collection of rows of pixels where each row of pixels is represented as a sum of waves of greyscale intensity.

First you select a single row from an image.

Then you apply the Fourier transform to represent the row as a collection of waves.

What I don't understand is, if we can get the frequencies for each row and accurately reconstruct what a row of the image looks like via frequency encoding, and if we already know where each row is in relation to the other rows (position of the blue line), why do we need to do the same basic thing along a different dimension (the y-axis using phase encoding)? Isn't it sufficient to simply stack the rows to get the full image?

• Can I please ask if this was resolved? – A_A Jul 7 '20 at 16:28

The reality (as in physical reality, the phenomenon) is that a pixel's "value" is determined both by what is happening along the X dimension and the Y dimension (in k-space).

If you want to reconstruct an image you have to do it from **two spatial sinusoidal waves.

This is represented in the $$f[m,n] \cdot e^{-j 2 \pi (u m + v n)}$$ part of the DFT. This is the product that we sum along the $$u$$ and $$v$$ directions.

Notice here, that to obtain one $$u,v$$ value you need to evaluate sinusoids in both the $$u$$ and $$v$$ directions. And vice-versa of course, meaning that the grey level value of one pixel is decomposed in the coefficients for both sinusoids along the $$u$$ and $$v$$ directions. If you only run one of them, you get only HALF the story.

If you reconstruct an image from rows, you synthesize grey level variation from just one direction. You know how a pixel's value varies with respect to its left and right neighbours but not its top and bottom neighbours.

Here is a mental experiment: Take an image and run DFTs along the rows (that is, the horizontal direction, as per the recipe that motivated this question). Now take the original image and add 42 to the pixels of the rows of the upper half (this looks like a step in the vertical direction). What is the effect of this? You are only introducing a DC to the ROW DFTS, other than this, the rest of the spectrum is exactly the same.

You can choose to get even more adventurous in that vertical direction and modulate the pixels by sinusoids. They will go completely amiss, why?

Because that modulation, along the vertical direction only introduces some "disturbance" to the DC component of the horizontal direction. It is impossible to pick up anything else unless you "check" for it, by evaluating the DFT along the vertical dimension too.

And you can see this happening in $$F[u,v] = \sum_m \sum_n x[m,n] e^{-j 2 \pi (u*m + v*n)}$$ because the sums are nested as well as when you apply the DFT twice because you first apply it on the rows (now you know how a pixel varies with respect to its left-right neighbours) and then you apply it along the columns of the ROWS DFT (now you know how a pixel varies with respect to its top and bottom neighbours).

Hope this (and to an extent this) helps.

in MRI, you don't start with the image as pixels in spatial domain, but with the k-space data!

So, you don't "construct k-space from the image", you "construct the image from k-space", which takes a 2D inverse Fourier transform.

And that's not "do it row-by-row"; that is "do it on all rows, then all columns of the result".

• Right, I understand that you don't start with the image, since that would defeat the purpose of the MRI. I guess what I'm asking is, why bother tracking the columns of k-space if you can just run the inverse Fourier transform on the nth row in k-space to get the nth row in the image, do this each row, and then stack all the resulting image rows to get the full image? Actually, as I read your answer more carefully I see you said that it's not "row by row." – user554481 Jun 25 '20 at 22:09
• Based on what I've read on this website (mriquestions.com/locations-in-k-space.html), I think the answer to my question (posed in the above comment) is that a single row in k-space isn't sufficient to reconstruct a single row in the image because each pixel in the image maps to every point in k-space, so then I guess a followup question would be: is the image analogy flawed? Should I ignore it because it is misleading? – user554481 Jun 25 '20 at 22:10
• @user554481 because the physics doesn't deliver a row-wise fourier transform of the image, but a 2D fourier transform. I think the example shown by the website you were referring to hence isn't wrong, but incomplete. You need to do a column-wise FT on the result of all the row transforms, too. – Marcus Müller Jun 26 '20 at 6:34


text:
## The existence of periodic solutions of $$f'(x)=-\alpha f(x-1)(1+f(x))$$.(English)Zbl 0106.29504

### Keywords:

ordinary differential equations
Full Text:

### References:

 [1] Wright, E.M., A non-linear difference-differential equation, J. reine angew. math., 194, 66-87, (1955) · Zbl 0064.34203 [2] Cunningham, W.J., A non-linear differential-difference equation of growth, (), 709-713 · Zbl 0055.31601 [3] Kakutani, S.; Markus, L., On the non-linear difference-differential equation y′(t) = [A − by(t − τ)] y(t), (), 1-18 · Zbl 0082.30301 [4] Browder, Felix E., On a generalization of the Schauder fixed point theorem, Duke math. J., 26, 291-303, (1959) · Zbl 0086.10203 [5] Jones, G.Stephen, Asymptotic behavior and periodic solutions of a nonlinear differential-difference equation, (), June · Zbl 0099.29502 [6] Jones, G.Stephen, On the nonlinear differential-difference equation $$ƒ′(x) = − αƒ(x − 1)[1 + ƒ(x)]$$, J. math. anal. and appl., 4, No. 3, 440-469, (1962) · Zbl 0106.29503
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
Follow the Installation Guide to setup the new node. After the node is added to the cluster (StorPool services are started), update the /etc/storpool.conf on all nodes:

Attention

The change for SP_EXPECTED_NODES must happen ONLY AFTER all nodes are up and in the cluster (in storpool net list), otherwise a large expansion can flap the cluster.

1. If this is a voting node (usually all server nodes are voting, and client only nodes are non-voting), increase the value of SP_EXPECTED_NODES. See the User’s Guide for details.

2. Add section for the new node with node specific settings.

3. Copy the updated storpool.conf file to all nodes in the cluster. There is no need to restart any services after this change.

Attention

Since rel.18.02 it is important that each node has valid configuration sections for all nodes in the cluster in its local /etc/storpool.conf file. Keep consistent /etc/storpool.conf files across all nodes in the cluster.

## 2. Remove a Node from Cluster¶

1. Notify StorPool support that a node will be decommissioned and monitoring and notifications shall be stopped for this node.

2. If this is a server node, re-balance out all data from the disks of this node:

For each disk on this node execute:

# storpool disk <diskID> softEject

After all disks are marked as softEject, run balancer:

# /usr/lib/storpool/balancer.sh -F -c0
# storpool balancer commit

Note

This operation may take several hours to complete, depending on the amount of data to be relocated and the load of the cluster.

3. Wait for the relocator to complete before the node is disconnected from the cluster. Monitor the rebalancing progress with:

# storpool relocator status

4. If the node being removed is configured as voting, verify that there will be enough voting nodes remaining in the cluster, when this node is disconnected. Check expected and actual number of voting nodes in the cluster with:

# storpool net list
...
Quorum status: 4 voting beacons up out of 4 expected

Attention

After the node is removed, the number of remaining voting nodes shall be more than 50% of the expected nodes listed above. If this requirement is not satisfied, decrease the number of expected nodes before disconnecting the node (see below).

5. After re-balancing is completed, disconnect the node form the cluster by:

# systemctl disable --now storpool_beacon.service storpool_stat.service storpool_abrtsync.service

Check that the node is not part of the cluster anymore with:

# storpool service list

The node can be physically disconnected form the storage network.

6. Update /etc/storpool.conf on all remaining nodes in the cluster by:

6.1. If this is a voting node, decrease SP_EXPECTED_NODES.

6.2. Remove the node-specific section from /etc/storpool.conf

6.3. Copy the updated storpool.conf file to all nodes in the cluster. There is no need to restart any services after this change.

7. After the /etc/storpool.conf is updated, if the number of expected voting nodes in the cluster was reduced, make the new value active by executing the following on the current active management node:

# echo "expected ${EXPECTED}" | nc -uU /var/run/storpool/beacon.cmd.sock  , where ${EXPECTED} is the new number of expected voting nodes. (e.g. echo "expected 3" | nc -uU /var/run/storpool/beacon.cmd.sock).

Check the expected number if voting nodes is correct with:

# storpool net list


text:
# The Impact On IC Silicon Area When Using A Custom Design Grid

December 08, 2017, anysilicon

Using a custom design grid in an IC layout offers many important advantages, but there is a potential price to pay in using them, particularly in terms of increased IC area. In this article we analyse the actual cost implications in detail.

Key advantages of a IC Layout Design Grid:

• Improved uniformity across a design (conductor spacing, width & density)
• Reduced lateral capacitive coupling
• Better control of density requirements
• Design rule clean by construction
• Enhanced design for manufacturability
• Reduced layout time (less requirements to zoom in/out, use of rulers, no need to be concerned about DRC fixes)
• Easier to migrate layout from one technology to another (between foundries and/or between nodes)

Overall, grids make the layout process faster, more uniform and guarantee a DFM clean layout by construction. However, whilst these advantages are likely to reduce both development costs of and cost of final silicon, engineers should also be aware that there are also some disadvantages to using custom grids.

Key disadvantages of a IC Layout Design Grid:

• Placing devices on design grid can be time consuming (automation can help)
• Schematic designs which are not optimised for a custom design grid, can potentially be slower to layout
• Potential increase in silicon area!

By far, the largest concern about implementing a gridded design, is the potential area cost due to using non-minimum metal, OD and poly spacing in the layout.

There are two places where conductor spacing can impact silicon area – device spacing (particularly when devices are placed as arrays) and routing channels. Here we will analyse the area cost of using a design grid in both occurrences.

Cost analysis – device arrays

The boundaries above represent the device/cell area, plus half minimum conductor spacing on all sides, such that when the devices are placed down with abutting boundaries, device spacing is adhered to. By snapping a device (or cell) to a design grid, you increase the placement boundary area, effectively increasing the device area.

When the devices are placed as an array, we can analyse the area of both the minimum rule boundary and the gridded boundary:

Minimum Rule                                                                    Design Grid

$A = ( N_{x} \times x) \times (N_{y} \times y)$                 $A+\Delta A=(Nx \times(x+\Delta x))\times(Ny \times(y+\Delta y))$

From this we can now determine the factor by which the area has increased:

$Area Increase= \frac{A +\Delta{A}}{A}$

$Area Increase = \frac{( N_{x} \times (x + \Delta{x})) \times (N_{y} \times (y+ \Delta{y}))}{( N_{x} \times x) \times (N_{y} \times y)}$

$Area Increase = \frac{(x + \Delta{x}) \times (y+ \Delta{y})}{x \times y} Area increase = \frac{xy + x\Delta{y} + y\Delta{x} + \Delta{x}\Delta{y}}{xy}$

$Area increase = \frac{xy}{xy} + \frac{x\Delta{y}}{xy} + \frac{y\Delta{x}}{xy} + \frac{\Delta{x}\Delta{y}}{xy} is 1 + \frac{\Delta{x}}{x} + \frac{\Delta{y}}{y} + \frac{\Delta{x}\Delta{y}}{xy}$
$Given that the factor \frac{\Delta{x}\Delta{y}}{xy} will be \ll than either \frac{\Delta{x}}{x} or \frac{\Delta{y}}{y} it can be ignored.$

So the overall increase in area is:

Area Increase=    $1 + \frac{\Delta{x}}{x} + \frac{\Delta{y}}{y}$

Some very important points are worth observing from this analysis:

• The larger x is with respect to Δx and/or y is with respect to Δy, then the smaller the area increase will be. So the larger the device size, the smaller the impact will be on silicon area when using design grid.
• If device sizes can be chosen such that y and x are already on (or close to) a design pitch, such that Δx and Δy are zero (or small), then the smaller the impact will be on silicon area.

Practical Example:

If we take a practical example of a minimum length MOS device on a generic 28nm technology.

• Poly to poly spacing (100nm in this case) is the dominant spacing.

• The boundary width extends for 50nm on either side of the dummy poly stripes, meaning there will be the minimum 100nm horizontal spacing between stripes of adjacent cells.

• The boundary width is 390nm

• The height of the poly stripes is 580nm

• Allowing for poly to poly vertical spacing of 100nm between cells, the boundary height is 680nm.

• Device boundary is x=390nm y=680nm

• Total device area =265,200nm²

The device, when arrayed up, will adhere to minimum poly to poly spacing on all sides

If we now apply a layout design grid of 80nm to this cell and its boundary, ensuring the centre of each device will be on grid and that minimum poly to poly spacing is not violated, we can analyse the cost in area. (80nm is an arbitrarily chosen value)

Currently, device centre to centre spacing is 390m in the horizontal direction (minimum rule)

• To snap the devices to an 80nm grid, this spacing would need to increase by 10nm, so that centre to centre spacing would be 400nm (an integer multiple of the design grid).
• The boundary of each cell would increase in the x axis by 5nm ( Δx=5nm)

The device spacing (centre to centre) in the vertical direction is 680nm

• To snap the devices to an 80nm grid, this spacing would need to increase by 40nm so that centre to centre spacing would be 720nm.
• The boundary of each cell would increase in the y axis by 20nm ( Δy=20nm)

From this increase, we can calculate the total area increase

Area Increase = 1 + Δγ + Δx     →     1 + 20nm    + 5 nm       →   1 + 0.029 + 0,0128  → 1.04
γ       x                   680nm     390nm

So there is a 4% increase in area when implementing an 80nm design grid.

Minimum Rule Boundary                                    Design Grid Boundary

It is worth noting that with a different design grid (i.e. 65nm) , Δχ would be 0nm and Δγ would be 17.5nm, leading to a 2.5% increase in area. This increase could be reduced further by either choosing an “on grid” device width (i.e. changing from current width of 210nm to 245nm), leading to no increase in area at all. Optimising schematic designs for adherence to layout design grids, reduces area cost.

Cost analysis – interconnect

Minimum Rule                                                               Design Grid

______________________________________________________________

Amin = W. Nw + (S x (nW -1))                               Agrid = W.Nw + ( Sgrd X (Nw – 1))

Amin = W.Nw + S.Nw – S                                      Agrid = W.Nw + Sgrid.Nw – Sgrid

Amin = ((W + S) X Nw) – S                                  Agrid =  ((W + Sgrid) x Nw) – Sgrid

For large routing channels ((W + S) x Nw) – S ≈ ((W + S) x Nw) as one wire spacing is small in the grander scheme of things.

Amin = ((W  + S) x Nw)                                      Agrid = ((W + Sgrid)xNw)

Area Increase =  Agrid    →  ((W + Sgrid) x Nw)      →   W + Sgrid

Amin            ((W + S) x Nw)                   W + S

Where

• Width = W; Number of wires (Nwires) = Nw; Spacing = S; Grid spacing = Sgrid

Practical Example:

If we take a practical example of a generic 28nm technology where W=100nm and S=60nm, track spacing, centre to centre would be 160nm. As this is already an integer multiple of the 80nm design grid, Sgrid would also be 60nm, so there would be no increase in area.

However, if we were to choose a different design grid (for example 65nm), track spacing Sgrid, would have to be increased to 95nm (from 60nm) to ensure all tracks were centred on grid.

Area Increase = Agrid      →   W + Sgrid     →   100nm + 95nm    →     1.218

Amin                 W + S             100nm + 60 nm

In this case it would lead to a ~ 22% increase in routing area! However it is very important to note, that with increasing metal layer stacks and requirements for minimum and maximum local poly density, most routing now takes place either between the spaced devices and/or over devices, so the requirement for actual routing channels has reduced. Thus the increase in area for routing does not necessarily lend itself directly in an increase in silicon area.

Final thoughts

With the advent of multi-patterning at 20nm and FinFET device pitches at 16nm, the requirements for pitched based, uniform layout designs increases. As semiengineering.com’s Mark Lapedus confirmed when discussing 10 and 7nm design, grids are where the industry is going: “There is a general move towards track and grid based layout forms. Expect this trend to increase moving forwards.”

This is a guest post by: Oleg Oncea from IC Mask Design


text:
# User:Nuri Purswani/NetworkReconstruction/ProjectOverview/Classes

Algorithms for Biological Network Reconstruction from data

 Home Project Overview Algorithms Results Discussion Software References
Classes of Network Inference Algorithms

The task of biological network inference can be done at different scales [2]:

• Inference of gene-sequence interactions.
• Inference of gene-gene interactions.

The methods considered in this project focus on gene-gene interactions, although the implementations are defined in a more general fashion, suitable for solving any system identification problem. The four main types of existing network reconstruction algorithms, along with their assumptions and limitations are summarised below (provide references to all):

## Clustering

The principle between this type of method is that genes that are co-expressed are likely to be functionally related. Quantification of "relatedness" between genes requires calculation employing some form of distance measure. Common distance measures include: eucledian distance, pearson correlation, spellman-rank...[3]. The main limitations to these methods include:

• Their inability to precisely infer gene-gene interactions: genes may be co-expressed, but clustering methods are unable to identify the precise interactions between genes.
• "There is no one size that fits all": Clustering methods impose a particular structure on the dataset of interest[3]. So out of the various published algorithms, there is no guarantee that they will return the correct structure of the datasets.

## Bayesian Networks

Bayesian networks are graph based models that capture relations of conditional independence between variables[4]. Markovian assumptions apply to them [5 Ref Markov Assumption], which states that any given node in a directed acyclic graph is independent of its non-descendants, given its parents. This means that:

• Static bayesian networks (i.e. networks that infer biological relationships from steady state data) are limited in their usefulness to interpret biological information. One of the common characteristics of biological processes is the presence of feedback, which is not captured by this rule of conditional independence. (draw a diagram)
• Dynamic bayesian networks overcome this problem, by using time-series data as input.
• Advantage-they are able to cope with noisy data and stochasticity

Bayesian inference algorithms commonly utilise optimisation procedures such as simulated annealing, expectation maximization algorithm, etc, to maximise a score of observing a particular data structure given a set of parameters. Following from Bayes' rule:

${\displaystyle P(G|D)={\frac {P(D|G)*P(G)}{P(D)}}}$

Where ${\displaystyle P(G|D)}$ is the score we are trying to maximise for a parameter ${\displaystyle G}$ given the observed data ${\displaystyle D}$. Scoring schemes also include steps that penalize connections such as the bayesian information criterion, aic and dirichlet[3]. These will be re-visited again in the next section.(expand on bayesian networks)

## Information Theory

Information theoretic approaches use the mutual information measure (see equation below- NUMBER EQUATIONS!) to quantify dependences between a pair of genes i and j. Depending on the value of the threshold set, the edges of the dependency are set to zero or 1. The general formula for mutual information is: [Also provide references to ARACNE and mut info algorithms]

${\displaystyle M_{ij}=H_{i}+H_{j}-H_{ij}}$

where ${\displaystyle H_{i}}$ is the entropy of a given quantity:

${\displaystyle -\sum _{i=1}^{n}p(x_{k})log(p(x_{k}))}$

## Ordinary Differential Equations

These involve inference of parameters ${\displaystyle A,B,C,D}$ for models in the form:

${\displaystyle {\frac {dx}{dt}}=Ax+By}$

${\displaystyle {\frac {dy}{dt}}=Cy+Dx}$

where ${\displaystyle x}$ and ${\displaystyle y}$ are species in the biological network we are trying to infer.


text:
187- Syllabus

Math 187 Section 3: Discrete and Foundational Mathematics I.
Instructor: Andrés Caicedo.
Contact Information: See here.
Time: MTuWF 1:40-2:30 pm.
Place: Mathematics/Geosciences building, Room 120.
Office Hours: MF 12:40-1:30 pm.

Text:

1. Proof: Introduction to Higher Mathematics. By Warren W. Esty and Norah C. Esty. Fifth edition.
2. The proof is in the Pudding. The Changing Nature of Mathematical Proof. By Steven G. Krantz. Springer, 2011.

Contents: From the Course Descriptions in the Department’s site:

An introduction to the language and methods of reasoning used throughout mathematics and computer science, and to selected topics in discrete mathematics. Propositional and predicate logic; elementary set theory; introduction to proof techniques including mathematical induction; functions and relations; and basic principles of elementary number theory, combinatorial enumeration, and graph theory.

There are two components to this course. First, you will learn some topics in discrete mathematics (for example, counting techniques, a bit of graph theory, and number theory). Just as important, in this course you will learn how to read (and hopefully, understand) mathematical arguments, and how to write mathematical proofs. Ideally, at the end of the course you will be able to produce a few proofs of your own.

We will cover different topics from the Proof textbook, with varying degrees of emphasis. We will cover additional topics not in the textbook, mainly on graph theory. Appropriate references will be given in that case; if needed, notes will be posted on this blog. This page will be frequently updated with detailed week-to-week descriptions, including homework assignments.

The book by Krantz discusses changes to the concept of proof through history. Many examples are presented, as well as stories about practicing mathematicians. We will cover these through the term.

Detailed week to week description:

• August 22-26. Introduction. We begin by covering material from Chapter 1, sections 1.1 and 1.2, with additional examples. Homework problems: From Section 1.1, exercises A.1-A.12, B.1-B.16, C.2.
• August 29-September 2. Sections 1.2, 4.1, 1.3. Much more on Venn Diagrams can be found on the dynamic survey by Frank Ruskey and Mark Weston at the Electronic Journal of Combinatorics site. See also the article The Search for Simple Symmetric Venn Diagrams by Frank Ruskey, Carla D. Savage, and Stan Wagon, in the Notices of the American Mathematical Society, December  2006, Volume 53, Issue 11. In reference to section 1.3, it may be useful to read section 1.4, The foundations of logic, in Krantz’s book. Quiz 1. Homework problems: Section 1.2: A.1, A.4, A.19, A.26, A.28, A.33-46; Section 4.1: Resolve the conjectures C.3-C.9. Since Monday September 5th is a holiday, the 2nd homework is due September 7th at the beginning of lecture, and we will have the 2nd quiz that day in the last 20 minutes of  lecture.
• September 6-9. Sections 1.3-1.6. Please also read “Detecting cheaters” on the excellent blog by Bruce Schneier. Quiz 2. Homework problems: Section 1.4: A.1, A.8-A.11, A.18-A.20, B.5, B.7-B.9. Section 1.5: A.1-A.8. A.33-A.36, A.50, A.51, B.3, B.27.
• September 12-16. The P-vs-NP problem. Section 11.7 of Krantz’s book. Also, this handout on P, NP, and the P-vs-NP problem. Wikipedia has an excellent discussion of Boolean satisfiability, the example we are mostly focusing on. See also its page on 2-satisfiability, which is actually a problem solvable in polynomial time. Krom’s algorithm, discussed there, builds on the idea of the “resolution method”, so please read details of the method in this handout. (The handout goes into more details than we are covering now; we will revisit it later once we have talked about mathematical induction.) Quiz 3. Homework problems: Here. Due Friday September 23. (Quiz 4 will be on Tuesday as usual.)
• September 19-23. Quantifiers. Sections 2.1-2.3. Quiz 4. Homework problems: Section 2.1: A.1-A.12, B.4-B.9; Section 2.2: A.1-A.4, A.7-A.12, A.22-A.26, A.29-A.32, B.41-B.43, B.45-B.47. Recall that the first midterm is next week, on September 27.
• September 26-30. Sections 2.3, 2.5, 3.3. First midterm: Tuesday, September 27. Homework problems: Section 2.3: A.5-A.8, B.3-B.5 (note that the answer to B.5.b will be a formula in terms of both $k$ and $n$), B.21, B.28, B.31, B.32, B.121; Section 2.5: B.5, B.6, B.15-B.22, B.39.
• October 3-7. Sections 3.3, 3.4, 3.5. Quiz 5. Homework problems:  Section 3.4: A3, A4, A5, A7, B2, B4, B9, B17, B18, B19, C3, C5. In case you missed it, here is a link to the NOVA Profile on the brothers Chudnovsky.
• October 10-14. Sections 3.5, 6.1. Quiz 6. Homework problems: Section 3.5: A1, A4, A7, B1, B4, B5, B6, B9-B19, B24. I am not requiring that you turn in C1 or C2, but it may be a good idea to work on them. Section 6.1: A1-A7, B17-B19, B22-B24, B35, B37, B38. I have posted some extra credit problems here. Our first presentation will be this Wednesday, see here.
• October 17-21. Sections 3.5, 6.2, 6.3. Quiz 7. In case you missed it, here is a link to the TED talk by Cédric Villani. Homework problems:
1. Use induction to prove that $\displaystyle 1+\frac1{\sqrt2}+\frac1{\sqrt3}+\dots+\frac1{\sqrt n}<2\sqrt n$.
2. The arithmetic mean of $k$ numbers $a_1,a_2,\dots,a_k$ is their average, $AM=\displaystyle \frac{a_1+a_2+\dots+a_k}k$. Their geometric mean is $\displaystyle GM=\root k\of{a_1a_2\dots a_k}$. Show that if $k=2^n$ and all the numbers $a_1,a_2,\dots,a_k$ are positive, then $AM\ge GM$. (Actually, the result is true for all $k$, even if they are not powers of $2$, but the proof of this is more difficult.)
3. The Fibonnaci numbers are given by $F_1=1$, $F_2=1$, and $F_{n+2}=F_{n+1}+F_n$. Show that $F_n\le 2^n$. (On the other hand, Example 4 from section 3.5 shows that $F_n\ge (3/2)^{n-2}$. One sometimes combines these two results, by saying that the rate of growth of the Fibonacci sequence is exponential.)
4. Section 3.5: B.46, B.50.
• October 24-28. Sections 6.2, 6.3, 3.6 of the “Proof” textbook; Section 11.10 of Krantz’s book. Quiz 8. Homework problems: Section 6.2: A.9-A.16, B.8, B.9. Solve two of  B.22-B.27. B-30. Section 3.6: A.3, B.6, B.7, B.10. B.26, B.29, B.31, B.32, B.41. Our second presentation will be this Wednesday, see here. Here is a link to the official page of the Alan Turing Year. Recall that the second midterm is next week, on November 2.
• October 31-November 4. The second midterm is Wednesday, November 2; please do not forget to bring a blue book. There will be a review on Nov. 1. On Friday, Nov.4, we will start Section 6.3, on prime numbers. There is no homework due next week. Here are our grader’s solutions for last week’s homework.
• November 7-11. Sections 6.3, 6.4. Quiz 9. Homework problems: Section 6.3: A.1-A.6, B.24, B.28-B.31, B.40, B.44, B.52, B.55. Section 6.4: A.2-A.6, A.9, B.1, B.8, B.20, B.21, C.1.
• November 14-18. Basic combinatorics (counting). We will be following the book Counting and configurations, by J. Herman, R. Kucera, and J. Simsa; Springer, Canadian Mathematical Society (2003). I will distribute a handout, on their sections 1.1, 1.2, 1.5(1-5). Quiz 10. Homework problems: From the handout: 1.3.1, 1.6.1, 1.6.2, 2.3.1, 2.3.3, 2.3.5, 2.6.2, 2.9.1, 2.9.5, 2.12.1, 2.12.4, 2.12.7, 2.19.1-6, 5.5.1.
• November 21-25. Thanksgiving break. Happy thanksgiving!
• November 28-December 2. The binomial theorem. Basic theory of functions. For the binomial theorem, we will follow Section 1.7 of the book Combinatorics by R. Merris; John Wiley & Sons, Inc. (2003). For functions, see Sections 5.1 and 5.2 of the Proof book. Quiz 11. Homework problems: From the handout: 1(b),(e),(i), 2(a),(d),(f),(i), 4, 6, 7, 11 (Hint for 11(b): You may argue by induction, and in the inductive step use the binomial theorem and 11(a). [There are other arguments that do not require induction.]) From the Proof book: 5.1.A1, A4, A7, A14, A17, A18, B1, B39.
• December 5-9. Dead week. We will cover Section 5.2 and, depending on time, the basic theory of relations, including equivalence relations (I will distribute a handout with these topics). We will have a review at the end. (Optional) Quiz 12. Optional homework: 5.2.A1, A6, A8, A12, B22, B23, B24. Remember the final exam is Wednesday, December 14, 1-3 pm. This exam is cumulative; please bring a blue book.
• December 14. Final exam. It was a pleasure having you in my class!

Presentations: Here is the list of all presentations we had, including links to some of them.

Prerequisites: Math 143, Math 147, or satisfactory placement score.

Quizzes: There will be weekly quizzes, on the last 20 minutes of Tuesday’s lecture (not on August 24). Each quiz will evaluate, roughly, the material covered the previous week. You are not allowed to only show up about 20 minutes before the end of the lecture in order to take the quiz; if you show up only for the quiz, your score is 0. If you fail to take a quiz, it will be scored as 0. The lowest score will be dropped.

For each quiz, I will provide you with a page with the question(s) printed. You may use this page to solve the questions. You need to bring any additional pieces of paper you may require. If a quiz will require more than 20 minutes, I will inform in advance, both in lecture and in this page.

Notes from class, textbooks, and calculators, are allowed during exams and quizzes. Bring your own pen, pencil, eraser, etc.

Homework: There is weekly homework, due Tuesdays at the beginning of lecture; you are welcome to turn in your homework early, but I will not accept homework past Tuesdays at 1:40 pm. The homework covers the material from the previous week, and it is a good idea to work daily on the homework problems corresponding to the material covered that day. During office hours, you are welcome to ask about problems from the assigned sets (or any other problems you find interesting). Frequently, some (but not necessarily all) of the problems from the quizzes will be fairly close, if not outright identical, to homework problems.

Following Otis Kenny‘s suggestion, your homework must follow the format developed by the mathematics department at Harvey Mudd College; it does not need to be typeset. You will find that format at this link. If you do not use this style, your homework will be graded as 0.

Extra credit: I may assign a few challenging problems through the term. Additionally, you may volunteer to present in class one of the stories covered in Krantz’s book, or a similar story. Let me know, and we will schedule a 10-15 minute presentation.

Exams: There will be 2 in-class exams and a comprehensive final exam.

• Exam 1: Tuesday, September 27.
• Exam 2: Wednesday, November 2.
• Final exam: Wednesday, December 14. 1-3 pm. This exam is cumulative.

Dates and times are non-negotiable. Failure to take a exam will be graded as a score of 0. There will be no make up for the final exam. For the in-class exams, a make up can be arranged if I am notified prior to the exam date and a valid reason is presented; keep in mind that make up exams will be more difficult than regular in-class exams.

You need to bring blue books to the exams.

• Quizzes: 20%. (Each quiz weighs the same towards the final grade.)
• Homework: 20%. (Each homework set weighs the same towards the final grade.)
• Exam 1: 20%.
• Exam 2: 20%.
• Final exam: 20%.

• If your final score is 90 or higher, you receive an A.
• If it is 80 or higher, you receive at least a B.
• If it is 70 or higher, you receive at least a C.
• If it is 60 or higher, you receive a D.
• There will be a curve at the end (which may increase your grade, never decrease it), and plus and minus grades might be used for grades near the top or bottom of a grade range.

Attendance: Not required, but encouraged. Any material covered in lecture, or assigned as homework, may be used in quizzes and exams, even if it is not discussed in the textbooks. I will use this website to post any additional information, and encourage you to use the comments feature, but (in general) I will not post here standard content covered in the textbooks and in class. If you leave a comment, please use your full name, which will simplify my life filtering spam out.

7 Responses to 187- Syllabus

1. Kevin Byrne says:

Hello Dr. Caicedo, I had a couple questions. First, is there anywhere I can find some of the answers to the textbook questions? Or someway I can verify if I’m doing these right? Also, would you prefer questions concerning homework problems posted here or somewhere else?

2. Hi Kevin.

I don’t think the answers are available, sorry. One way to verify if what you are doing is right is to check during office hours. You may also want to check with other students, usually many doubts can be solved quickly that way.

Questions about homework problems are fine here, but if the question is about verifying that your approach works, or whether your answer is right, it is better if you ask me directly or by email.

3. David Miller says:

Hello Dr. Caicedo,

I am having trouble getting started on Section 3.4 problems B4, B9, C3, and C5. Would you offer some hints on how to approach these? Are there prior results that must be considered? Are there multiple cases that need to be considered? Any help on getting started on these problems would be much appreciated. Thanks.

• Hi David,

Here is a hint for B4: You want to argue by contradiction, assuming that there are integers $a$ and $b$ that satisfy the given equation. Now, divide the argument into two cases: Can $b$ be even? Can it be odd?

For B9, the hint is to try to argue following closely the proof we gave for the irrationality of $sqrt2$, so you need to examine that proof, and see whether you can “adapt it” to prove the irrationality of $sqrt3$. The key point in that proof was when we arrived at an equation of the form $m^2=2n^2$ and we used it to conclude, first that $m$ was even and, then, that $n$ was also even. If you follow the same idea in this case, you will now arrive instead at an equation of the form $m^2=3n^2$. Now, rather than deducing that $m$ is even, try to deduce from this that $m$ must be a multiple of 3.

How? Well, try a proof by contradiction! If $m$ is not a multiple of 3, then when you divide it by 3, it leaves a remainder, which will be 1 or 2, right, so $m$ has the form $3k+1$ or $3k+2$. Show that in either case, $m^2$ is *not* a multiple of 3.

• For C3, you argue by contradiction, assuming that the equation has a rational root. Following the hint the book gives, we may assume the root is $p/q$ where $p$ and $q$ have no common factors. Multiply the equation by $q^2$, you should arrive at something like $ap^2+bpq+cq^2=0$.

Now, the argument requires 3 steps: 1. Show that $p$ must be odd. To show this, suppose instead that $p$ is even, and derive a contradiction. Here you will need to use the assumption that $a,b,c$ are odd integers.

2. Show that $q$ must be odd. To do this, the argument should be very similar to what you did in the previous step.

3. Now that you know that $p$ and $q$ are odd, and that $a,b,c$ are also odd, explain why it is not possible for $ap^2+bpq+cq^2$ to be 0.

Once you finish the third step, you have reached a contradiction: You have that $ap^2+bpq+cq^2=0$, and you also have that it is *not* equal to 0.

For C5, it may be useful to introduce some notation, because you want to examine what a sum of three consecutive positive integers looks like. Say, the first one is $k$. What are the other two? What is their sum? Now that you have a formula for the sum, can this be a prime number? Be careful with this last step, you may have to consider a couple of cases.

Hope this helps.

4. David Miller says:

Hello Dr. Caicedo,

I’m not certain that I’m doing these problems correctly, but if I am, I have a question. For example, with problem 1e, “What is the coeficient of x^5 in the binamial expansion of (1+2x)^7”. Is the desired coeficient just the result of (7¦5), i.e. 21? Or after factoring out the 4 from 4x^2, so 84?

(1+2x)^7:

∑_(k=0 -> 7)〖(7¦5) (1^5) (2x)^2 〗
= [7!/((5!)(2!))] * (4x^2 )
= 21(4x^2 )
= 84x^2

Thanks,
Dave

• Hi Dave, it is not just $binom75$, but it is not 84 either (you want the coefficient of $x^5$, not of $x^2$), it should be $binom75times 2^5$ or something like this.


text:
Definitions
Nearby Words

# Farey sequence

[fair-ee]
In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size.

Each Farey sequence starts with the value 0, denoted by the fraction 01, and ends with the value 1, denoted by the fraction 11 (although some authors omit these terms).

A Farey sequence is sometimes called a Farey series, which is not strictly correct, because the terms are not summed.

## Examples

The Farey sequences of orders 1 to 8 are :
F1 = {01, 11}
F2 = {01, 12, 11}
F3 = {01, 13, 12, 23, 11}
F4 = {01, 14, 13, 12, 23, 34, 11}
F5 = {01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11}
F6 = {01, 16, 15, 14, 13, 25, 12, 35, 23, 34, 45, 56, 11}
F7 = {01, 17, 16, 15, 14, 27, 13, 25, 37, 12, 47, 35, 23, 57, 34, 45, 56, 67, 11}
F8 = {01, 18, 17, 16, 15, 14, 27, 13, 38, 25, 37, 12, 47, 35, 58, 23, 57, 34, 45, 56, 67, 78, 11}

## History

The history of 'Farey series' is very curious — Hardy & Wright (1979) Chapter III

... once again the man whose name was given to a mathematical relation was not the original discoverer so far as the records go. — Beiler (1964) Chapter XVI

Farey sequences are named after the British geologist John Farey, Sr., whose letter about these sequences was published in the Philosophical Magazine in 1816. Farey conjectured that each new term in a Farey sequence expansion is the mediant of its neighbours — however, so far as is known, he did not prove this property. Farey's letter was read by Cauchy, who provided a proof in his Exercises de mathématique, and attributed this result to Farey. In fact, another mathematician, C. Haros, had published similar results in 1802 which were almost certainly not known either to Farey or to Cauchy. Thus it was a historical accident that linked Farey's name with these sequences.

## Properties

### Sequence length

The Farey sequence of order n contains all of the members of the Farey sequences of lower orders. In particular Fn contains all of the members of Fn−1, and also contains an additional fraction for each number that is less than n and coprime to n. Thus F6 consists of F5 together with the fractions 16 and 56. The middle term of a Farey sequence Fn is always 12, for n > 1.

From this, we can relate the lengths of Fn and Fn−1 using Euler's totient function φ(n) :-

$|F_n| = |F_\left\{n-1\right\}| + varphi\left(n\right)$

Using the fact that |F1| = 2, we can derive an expression for the length of Fn :-

$|F_n| = 1 + sum_\left\{m=1\right\}^n varphi\left(m\right)$

The asymptotic behaviour of |Fn| is :-

$|F_n| sim frac \left\{3n^2\right\}\left\{pi^2\right\}$

### Farey neighbours

Fractions which are neighbouring terms in any Farey sequence are known as a Farey pair and have the following properties.

If ab and cd are neighbours in a Farey sequence, with ab < cd, then their difference cd − ab is equal to 1bd. Since

$frac\left\{c\right\}\left\{d\right\} - frac\left\{a\right\}\left\{b\right\} = frac\left\{bc - ad\right\}\left\{bd\right\}$,

this is equivalent to saying that

Thus 13 and 25 are neighbours in F5, and their difference is 115.

The converse is also true. If

for positive integers a,b,c and d with a < b and c < d then ab and cd will be neighbours in the Farey sequence of order max(b,d).

If pq has neighbours ab and cd in some Farey sequence, with

ab < pq < cd

then pq is the mediant of ab and cd — in other words,

$frac\left\{p\right\}\left\{q\right\} = frac\left\{a + c\right\}\left\{b + d\right\}$.

And if ab and cd are neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is increased is

$frac\left\{a+c\right\}\left\{b+d\right\}$,

which first appears in the Farey sequence of order b + d.

Thus the first term to appear between 13 and 25 is 38, which appears in F8.

The Stern-Brocot tree is a data structure showing how the sequence is built up from 0 (= 01) and 1 (= 11), by taking successive mediants.

Fractions that appear as neighbours in a Farey sequence have closely related continued fraction expansions. Every fraction has two continued fraction expansions - in one the final term is 1; in the other the final term is greater than 1. If pq, which first appears in Farey sequence Fq, has continued fraction expansions

[0; a1, a2, …, an − 1, an, 1]
[0; a1, a2, …, an − 1, an + 1]

then the nearest neighbour of pq in Fq (which will be its neighbour with the larger denominator) has a continued fraction expansion

[0; a1, a2, …, an]

and its other neighbour has a continued fraction expansion

[0; a1, a2, …, an − 1]

Thus 38 has the two continued fraction expansions [0; 2, 1, 1, 1] and [0; 2, 1, 2], and its neighbours in F8 are 25, which can be expanded as [0; 2, 1, 1]; and 13, which can be expanded as [0; 2, 1].

### Ford circles

There is an interesting connection between Farey sequence and Ford circles.

For every fraction p/q (in its lowest terms) there is a Ford circle C[p/q], which is the circle with radius 1/(2q2) and centre at (p/q, 1/(2q2)). Two Ford circles for different fractions are either disjoint or they are tangent to one another - two Ford circles never intersect. If 0 < p/q < 1 then the Ford circles that are tangent to C[p/q] are precisely the Ford circles for fractions that are neighbours of p/q in some Farey sequence.

Thus C[2/5] is tangent to C[1/2], C[1/3], C[3/7], C[3/8] etc.

### Riemann Hypothesis

Farey sequences are used in two equivalent formulations of the Riemann hypothesis. Suppose the terms of $F_n$ are $\left\{a_\left\{k,n\right\} : k = 0, 1, ldots m_n\right\}$. Define $d_\left\{k,n\right\} = a_\left\{k,n\right\} - k/m_n$, in other words $d_\left\{k,n\right\}$ is the difference between the kth term of the nth Farey sequence, and the kth member of a set of the same number of points, distributed evenly on the unit interval. Franel and Landau proved that the two statements that $sum_\left\{k=1\right\}^\left\{m_n\right\} |d_\left\{k,n\right\}| = mathcal\left\{O\right\} \left(n^r\right)$ for any r>1/2, and that $sum_\left\{k=1\right\}^\left\{m_n\right\} d_\left\{k,n\right\}^2 = mathcal\left\{O\right\}\left(n^r\right)$ for any r>-1, are equivalent to the Riemann hypothesis.

## Simple algorithm

A surprisingly simple algorithm exists to generate the terms in either traditional order (ascending) or non-traditional order (descending):

"""Python function to print the nth Farey sequence, either ascending or descending.""" def farey(n, asc=True ):

`   if asc:`
`       a, b, c, d = 0, 1,  1  , n     # (*)`
`   else:`
`       a, b, c, d = 1, 1, n-1 , n     # (*)`
`   print "%d/%d" % (a,b)`
`   while (asc and c < n) or (not asc and a > 0):`
`       k = int((n + b)/d)`
`       a, b, c, d = c, d, k*c - a, k*d - b`
`       print "%d/%d" % (a,b)`

Brute force searches for solutions to Diophantine equations in rationals can often take advantage of the Farey series (to search only reduced forms). The lines marked (*) can also be modified to include any two adjacent terms so as to generate terms only larger (or smaller) than a given term.

## References

### Footnotes

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd Edition (Addison-Wesley, Boston, 1989); in particular, Sec. 4.5 (pp. 115-123), Bonus Problem 4.61 (pp. 150, 523-524), Sec. 4.9 (pp. 133-139), Sec. 9.3, Problem 9.3.6 (pp. 462-463). ISBN 0201558025.
• Linas Vepstas. The Minkowski Question Mark, GL(2,Z), and the Modular Group. http://linas.org/math/chap-minkowski.pdf reviews the isomorphisms of the Stern-Brocot Tree.
• Linas Vepstas. Symmetries of Period-Doubling Maps. http://linas.org/math/chap-takagi.pdf reviews connections between Farey Fractions and Fractals.