text:
Seifert surgery on knots via Reidemeister torsion and Casson-Walker-Lescop invariant II

# Seifert surgery on knots via Reidemeister torsion and Casson-Walker-Lescop invariant II

Teruhisa Kadokami, Noriko Maruyama and Tsuyoshi Sakai
June 3, 2015
###### Abstract

For a knot with in a homology -sphere, let be the result of -surgery on . We show that an appropriate assumption on the Reidemeister torsion of the universal abelian covering of implies , if is a Seifert fibered space.

00footnotetext: 2010 Mathematics Subject Classification: 11R04, 11R27, 57M25, 57M27. Keywords: Reidemeister torsion, Casson-Walker-Lescop invariant, Seifert fibered space.

## 1 Introduction

The first auther [Kd1] studied the Reidemister torsion of Seifert fibered homology lens spaces, and showed the following:

###### Theorem 1.1

([Kd1, Theorem 1.4]) Let be a knot in a homology -sphere such that the Alexander polynomial of is . The only surgeries on that may produce a Seifert fibered space with base and with have coefficients and , and produce Seifert fibered space with three singular fibers. Moreover (1) if the coefficient is , then the set of multiplicities is where , and (2) if the coefficient is , then the set of multiplicities is where .

It is conjectured that Seifert surgeries on non-trivial knots are integral (except some cases). We [KMS] have studied the -Seifert surgery, one of the remaining cases of the above theorem, by applying the Reidemister torsion and the Casson-Walker-Lescop invariant, and have given sufficient conditions to determine the integrality of ([KMS, Theorems 2.1, 2.3]).

In this paper, we give another condition for the integrality of (Theorem 2.1). Like as in [KMS], the condition is also suggested by computations for the figure eight knot ([KMS, Example 2.2]).

We note two differences of this paper from [KMS]; one is that the surgery coefficient appears in the condition instead of the Casson-Walker-Lescop invariant, and another is that we need more delicate estimation for the Dedekind sum to prove the result.

(1) Let be a homology -sphere, and let be a knot in . Then denotes the Alexander polynomial of , and denotes the result of -surgery on .

(2) The first author [Kd2] introduced the norm of polynomials and homology lens spaces: Let be a primitive -th root of unity. For an element of , denotes the norm of associated to the algebraic extension over . Let be a Laurent polynomial over . We define by

 |f(t)|d=|Nd(f(ζd))|=∣∣ ∣∣∏i∈(Z/dZ)×f(ζid)∣∣ ∣∣.

Let be a homology lens space with . Then there exists a knot in a homology -sphere such that ([BL, Lemma 2.1]). We define by

 |X|d=|ΔK(t)|d,

where is a divisor of . Then is a topological invariant of (Refer to [Kd2] for details).

(3) Let be a closed oriented -manifold. Then denotes the Lescop invariant of ([Le]). Note that .

## 2 Result

Let be a knot in a homology -sphere . Let be the result of -surgery on : . Let be the universal abelian covering of (i.e. the covering associated to ). Since , is the -fold unbranched covering.

In [KMS], we have defined by the following formula, if is defined:

 |K|(q,d):=|X|d.

Assume that the Alexander polynomial of is . Then, as noted in [KMS], and is defined.

We then have the following.

###### Theorem 2.1

Let be a knot in a homology 3-sphere . We assume the following.

(2.1) ,

(2.2) ,

(2.3) ,

(2.4) .

Then is not a Seifert fibered space.

###### Remark 2.2

Let be the figure eight knot in . Note that . Then by [KMS, Example 2.2]. Hence (2.4) holds if .

###### Remark 2.3

Theorem 2.1 seems to suggest studying the asymptotic behavior of as a function of .

## 3 An inequality for the Dedekind sum

To prove Theorem 2.1, we need the following inequality for the Dedekind sum ([RG]):

###### Proposition 3.1

([Ma, Lemma 3]) For an even integer and for an odd integer such that and , we have

 |s(q,p)|

where .

By this proposition, we immediately have the following.

###### Lemma 3.2

For an even integer and for an integer such that and , we have

 |s(q∗,p)|

Proof. By assumptions, there exists such that and . Hence by Proposition 3.1, we have

 |s(q∗,p)|=|s(q,p)|<(p−1)(p−5)24p

###### Remark 3.3

The estimation given in Proposition 3.1 has a natural application ([Ma]).

## 4 Proof of Theorem 2.1

Suppose that is a Seifert fibered space. Then, as shown in [KMS], we may assume that

: has a framed link presentation as in Figure 1,

where and .

Also as shown in [KMS], . Hence by (2.4),

 (αβ)2>4q2 (4.1)

By (2.1), (2.2) and [Le, 1.5 T2], we have . Hence , and hence

 |λ(M)|<αβ2 (4.2)

We now consider defined as follows:

 e:=q12α+q22β+q35.

According to the sign of , we treat two cases separetely: We first consider the case . Then the order of is . Since , , and . Hence by and [Le, Proposition 6.1.1], we have

 λ(M)=(−45)αβ+5β24α+5α24β+1120αβ−14−T (4.3)

where .

By (4.2), we have

 −αβ2<λ(M).

Hence by (4.3),

 −αβ2<(−45)αβ+5β24α+5α24β+1120αβ−14+|T|.

Consequently

 310αβ<−14+524αβ+524(αβ)+1120αβ+|T| (4.4)

As in [KMS], we show that implies a contradiction: Suppose that . Since , we have and . Hence

 35β<−14+524⋅2β+524+1120⋅2⋅3+|T|.

Since , , and as in [KMS], we have

 |T|≤|s(q1,2α)|+|s(q2,2β)|+|s(q3,5)|≤β3+15.

Hence

 35β<−14+548β+524+1120⋅6+(β3+15).

Thus

 (35−548−13)β<−14+524+1120⋅6+15.

Therefore

 39240β<1240(38+13)<39240.

We next show that implies a contradiction: Suppose that . By (4.1), . Since , . Hence . Since , . Hence

 q12+q22β+q35=110β

and hence we have the following equation.

 (5β)q1+5q2+(2β)q3=1 (4.5)

Since and are odd (see Figure 1), must be even. Since , we have . We then have

 (♯):q2≢±1(mod 2β).

In fact, since is odd, . Hence by (4.5),

 β+5q2≡1(mod 2β).

Now suppose that . Then . This is impossible since . Next suppose that . Then . This is also impossible since . Thus holds.

Substituing in (4.4),

 310β<−14+524β+524β+1120β+|T|

where (since ). By and Lemma 3.2,

 |s(q2,2β)|<2β24=β12.

Hence

 |T|≤|s(q2,2β)|+|s(q3,5)|<β12+15.

Since ,

 310β<−14+524β+524⋅8+1120⋅8+(β12+15).

Thus

 (310−524−112)β<−14+524⋅8+1120⋅8+15

and hence . This is a contradiction, and ends the proof in the case .

We finally consider the case . Then . By and [Le, Proposition 6.1.1], we have

 λ(M)=−{(−45)αβ+5β24α+5α24β+1120αβ−14+T}.

Remaining part of the proof is similar to that in the case .

This completes the proof of Theorem 2.1.

## References

• [BL] S. Boyer and D. Lines, Surgery formulae for Casson’s invariant and extensions to homology lens spaces, J. Reine Angew. Math., 45 (1990), 181–220.
• [Kd1] T. Kadokami, Reidemeister torsion of Seifert fibered homology lens spaces and Dehn surgery, Algebr. Geom. Topol., 7 (2007), 1509–1529.
• [Kd2] T. Kadokami, Reidemeister torsion and lens surgeries on knots in homology -spheres II, Top. Appl., 155, no.15 (2008), 1699–1707.
• [KMS] T. Kadokami, N.Maruyama and T. Sakai, Seifert surgery on knots via Reidemeister torsion and Casson-Walker-Lescop invariant, Top. Appl., 188 (2015), 64–73.
• [Le] C. Lescop, Global surgery formula for the Casson-Walker invariant, Ann. of Math. Studies, Princeton Univ. Press., 140 (1996).
• [Ma] N. Maruyama, On a distribution of rational homology 3-spheres captured by the CWL invariant, Preprint (2009).
• [RG] H. Rademacher and E. Grosswald, Dedekind sums, The Carus Mathematical Monograph, 16 (1972).

Department of Mathematics, East China Normal University,

Dongchuan-lu 500, Shanghai, 200241, China

Noriko Maruyama

Musashino Art University,

Ogawa 1-736, Kodaira, Tokyo 187-8505, Japan

maruyama@musabi.ac.jp

Tsuyoshi Sakai

Department of Mathematics, Nihon University,

3-25-40, Sakurajosui, Setagaya-ku, Tokyo 156-8550, Japan

You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minimum 40 characters and the title a minimum of 5 characters


text:
# Lab: Files

Assigned
Wednesday, Nov 7, 2018
Due
Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
Summary
In this laboratory, we explore file creation, file input, and file output in Scheme.

## Preparation

a. Skim through this lab to determine what kinds of tasks you’ll need to complete.

b. You should also review the reading on files in Scheme.

c. Make a copy of the code from the reading.

## Exercises

### Exercise 1: Summing values

The file /home/rebelsky/glimmer/samples/numbers.txt contains five hundred and twenty-eight natural numbers.

a. Use sum-of-file from the reading to determine their sum.

b. How would you quickly determine if your attempt to sum those numbers was correct?

Citation: That file was copied from a similar file produced by Mr. Stone.

### Exercise 2: File Length

Using sum-of-file (and its helpers) as a pattern, write a Scheme procedure, (file-size "file-name") that takes as argument a string that names a file and returns the number of characters in that file (that is, the number of times that read-char can be called to read a character from the file without returning the end-of-file object).

Note that you should not use read in your procedure.

### Exercise 3: Missing files

Find out what happens if sum-of-file or file-size is given a string that does not name any existing file.

### Exercise 4: Creating files

a. In the interactions pane, write a series of expressions that will create a file, my-info, with three lines, each of the form

• last name
• a comma
• first name
• a comma
• major
• a comma
• year

For example, the first line might read

Rebelsky,Samuel,Film Studies,2017

b. Determine what happens when you read that file back using file->lines.

c. Determine what happens when you read that file back using read-csv-file.

### Exercise 5: Reusing output files

The Scheme standard says that if you try to open an output port to a file that already exists, “the effect is unspecified”. That is, anything might happen. Hence, designers of a particular implementation of Scheme are free to do what they choose.

a. Find out through experimentation what DrRacket does in this situation.

b. Search the Web for the Racket documentation on open-output-file and find out how to overwrite an existing file.

### Exercise 6: Writing to files, revisited

a. Write a Scheme procedure, (student-info output-port last-name first-name major year) that writes one line in the form specified above.

b. Write a Scheme procedure (dump-info file-name list-of-data) that, given a list of student data, with each entry of the form (last first major year), writes all the data to the given file.

(dump-info "/home/username/Desktop/data.csv"
(list (list "Rebelsky" "Samuel" "Film Studies" 2017)
(list "Dent" "Stu" "Liberal Arts" 2021)
(list "K" "Russell" "Law" 1950)
(list "Again" "Mash" "Robotic Soccer" 2020)))

c. Confirm that your procedure works correctly by opening the file in DrRacket.

d. Confirm that your procedure works correctly by opening the file using read-csv-file.

## For those with extra time

### Extra 1: Displaying files

Write a procedure, (display-file filename), that takes the name of a file as a parameter and displays the contents of the file with each line preceded by its line number.

Please read directly from the file. You may not use file->lines, file->words, or file->chars in this definition.

### Extra 2: Finding divisors

Use the store-divisors procedure from the reading to draw up a list of the divisors of 120, storing them in a file named divisors-of-120. Examine the file afterwards and confirm that the answer is correct.

By the way, don’t give this procedure an extremely large number as argument – it’s much too slow. There are more efficient ways to find divisors!

### Extra 3: Counting vowels

Write a Scheme procedure that takes as arguments two file names (an input file and an output file), counts the number of occurrences of each vowel in the input file, and writes the result to the output file. Note that the output file should have the following form (with numbers in place of the number signs):

a,###
e,###
i,###
o,###
u,###

format: plain


text:
College Algebra

# 5.2Power Functions and Polynomial Functions

College Algebra5.2 Power Functions and Polynomial Functions

### Learning Objectives

In this section, you will:
• Identify power functions.
• Identify end behavior of power functions.
• Identify polynomial functions.
• Identify the degree and leading coefficient of polynomial functions.
Figure 1 (credit: Jason Bay, Flickr)

Suppose a certain species of bird thrives on a small island. Its population over the last few years is shown in Table 1.

 Year $2009 2009$ $2010 2010$ $2011 2011$ $2012 2012$ $2013 2013$ Bird Population $800 800$ $897 897$ $992 992$ $1,083 1,083$ $1,169 1,169$
Table 1

The population can be estimated using the function$P(t)=−0.3 t 3 +97t+800, P(t)=−0.3 t 3 +97t+800,$where$P(t) P(t)$represents the bird population on the island$t t$years after 2009. We can use this model to estimate the maximum bird population and when it will occur. We can also use this model to predict when the bird population will disappear from the island. In this section, we will examine functions that we can use to estimate and predict these types of changes.

### Identifying Power Functions

Before we can understand the bird problem, it will be helpful to understand a different type of function. A power function is a function with a single term that is the product of a real number, a coefficient, and a variable raised to a fixed real number.

As an example, consider functions for area or volume. The function for the area of a circle with radius$r r$ is

$A(r)=π r 2 A(r)=π r 2$

and the function for the volume of a sphere with radius$r r$ is

$V(r)= 4 3 π r 3 V(r)= 4 3 π r 3$

Both of these are examples of power functions because they consist of a coefficient,$π π$or$4 3 π, 4 3 π,$multiplied by a variable$r r$raised to a power.

### Power Function

A power function is a function that can be represented in the form

$f(x)=k x p f(x)=k x p$

where$k k$ and$p p$are real numbers, and$k k$ is known as the coefficient.

### Q&A

Is$f(x)= 2 x f(x)= 2 x$a power function?

No. A power function contains a variable base raised to a fixed power. This function has a constant base raised to a variable power. This is called an exponential function, not a power function.

### Example 1

#### Identifying Power Functions

Which of the following functions are power functions?

Try It #1

Which functions are power functions?

$f(x) = 2x⋅4 x 3 g(x) = − x 5 +5 x 3 h(x) = 2 x 5 −1 3 x 2 +4 f(x) = 2x⋅4 x 3 g(x) = − x 5 +5 x 3 h(x) = 2 x 5 −1 3 x 2 +4$

### Identifying End Behavior of Power Functions

Figure 2 shows the graphs of$f(x)= x 2 , g(x)= x 4 f(x)= x 2 , g(x)= x 4$and$h(x)= x 6 , h(x)= x 6 ,$which are all power functions with even, whole-number powers. Notice that these graphs have similar shapes, very much like that of the quadratic function in the toolkit. However, as the power increases, the graphs flatten somewhat near the origin and become steeper away from the origin.

Figure 2 Even-power functions

To describe the behavior as numbers become larger and larger, we use the idea of infinity. We use the symbol$∞ ∞$for positive infinity and$−∞ −∞$for negative infinity. When we say that “$x x$approaches infinity,” which can be symbolically written as$x→∞, x→∞,$we are describing a behavior; we are saying that$x x$is increasing without bound.

With the positive even-power function, as the input increases or decreases without bound, the output values become very large, positive numbers. Equivalently, we could describe this behavior by saying that as$x x$approaches positive or negative infinity, the$f( x ) f( x )$values increase without bound. In symbolic form, we could write

Figure 3 shows the graphs of$f(x)= x 3 , g(x)= x 5 , f(x)= x 3 , g(x)= x 5 ,$and$h(x)= x 7 , h(x)= x 7 ,$which are all power functions with odd, whole-number powers. Notice that these graphs look similar to the cubic function in the toolkit. Again, as the power increases, the graphs flatten near the origin and become steeper away from the origin.

Figure 3 Odd-power functions

These examples illustrate that functions of the form$f( x )= x n f( x )= x n$reveal symmetry of one kind or another. First, in Figure 2 we see that even functions of the formeven, are symmetric about the$y- y-$axis. In Figure 3 we see that odd functions of the form odd, are symmetric about the origin.

For these odd power functions, as$x x$ approaches negative infinity,$f( x ) f( x )$ decreases without bound. As$x x$ approaches positive infinity,$f( x ) f( x )$ increases without bound. In symbolic form we write

The behavior of the graph of a function as the input values get very small ($x→−∞ x→−∞$) and get very large ($x→∞ x→∞$) is referred to as the end behavior of the function. We can use words or symbols to describe end behavior.

Figure 4 shows the end behavior of power functions in the form$f(x)=k x n f(x)=k x n$where$n n$is a non-negative integer depending on the power and the constant.

Figure 4

### How To

Given a power function$f(x)=k x n f(x)=k x n$where$n n$is a non-negative integer, identify the end behavior.

1. Determine whether the power is even or odd.
2. Determine whether the constant is positive or negative.
3. Use Figure 4 to identify the end behavior.

### Example 2

#### Identifying the End Behavior of a Power Function

Describe the end behavior of the graph of$f(x)= x 8 . f(x)= x 8 .$

### Example 3

#### Identifying the End Behavior of a Power Function.

Describe the end behavior of the graph of$f(x)=− x 9 . f(x)=− x 9 .$

#### Analysis

We can check our work by using the table feature on a graphing utility.

$x x$ $f( x ) f( x )$
–10 1,000,000,000
–5 1,953,125
0 0
5 –1,953,125
10 –1,000,000,000
Table 2

We can see from Table 2 that, when we substitute very small values for$x, x,$the output is very large, and when we substitute very large values for$x, x,$the output is very small (meaning that it is a very large negative value).

Try It #2

Describe in words and symbols the end behavior of$f(x)=−5 x 4 . f(x)=−5 x 4 .$

### Identifying Polynomial Functions

An oil pipeline bursts in the Gulf of Mexico, causing an oil slick in a roughly circular shape. The slick is currently 24 miles in radius, but that radius is increasing by 8 miles each week. We want to write a formula for the area covered by the oil slick by combining two functions. The radius$r r$ of the spill depends on the number of weeks$w w$ that have passed. This relationship is linear.

$r(w)=24+8w r(w)=24+8w$

We can combine this with the formula for the area$A A$ of a circle.

$A(r)=π r 2 A(r)=π r 2$

Composing these functions gives a formula for the area in terms of weeks.

$A(w) = A(r(w)) = A(24+8w) = π (24+8w) 2 A(w) = A(r(w)) = A(24+8w) = π (24+8w) 2$

Multiplying gives the formula.

$A(w)=576π+384πw+64π w 2 A(w)=576π+384πw+64π w 2$

This formula is an example of a polynomial function. A polynomial function consists of either zero or the sum of a finite number of non-zero terms, each of which is a product of a number, called the coefficient of the term, and a variable raised to a non-negative integer power.

### Polynomial Functions

Let$n n$ be a non-negative integer. A polynomial function is a function that can be written in the form

$f(x)= a n x n + ... + a 2 x 2 + a 1 x+ a 0 f(x)= a n x n + ... + a 2 x 2 + a 1 x+ a 0$

This is called the general form of a polynomial function. Each$a i a i$ is a coefficient and can be any real number, but $a n a n$cannot = 0. Each expression$a i x i a i x i$ is a term of a polynomial function.

### Example 4

#### Identifying Polynomial Functions

Which of the following are polynomial functions?

$f(x) = 2 x 3 ⋅3x+4 g(x) = −x( x 2 −4) h(x) = 5 x+2 f(x) = 2 x 3 ⋅3x+4 g(x) = −x( x 2 −4) h(x) = 5 x+2$

### Identifying the Degree and Leading Coefficient of a Polynomial Function

Because of the form of a polynomial function, we can see an infinite variety in the number of terms and the power of the variable. Although the order of the terms in the polynomial function is not important for performing operations, we typically arrange the terms in descending order of power, or in general form. The degree of the polynomial is the highest power of the variable that occurs in the polynomial; it is the power of the first variable if the function is in general form. The leading term is the term containing the highest power of the variable, or the term with the highest degree. The leading coefficient is the coefficient of the leading term.

### Terminology of Polynomial Functions

We often rearrange polynomials so that the powers are descending.

When a polynomial is written in this way, we say that it is in general form.

### How To

Given a polynomial function, identify the degree and leading coefficient.

1. Find the highest power of$x x$ to determine the degree function.
2. Identify the term containing the highest power of$x x$ to find the leading term.
3. Identify the coefficient of the leading term.

### Example 5

#### Identifying the Degree and Leading Coefficient of a Polynomial Function

Identify the degree, leading term, and leading coefficient of the following polynomial functions.

$f(x) = 3+2 x 2 −4 x 3 g(t) = 5 t 5 −2 t 3 +7t h(p) = 6p− p 3 −2 f(x) = 3+2 x 2 −4 x 3 g(t) = 5 t 5 −2 t 3 +7t h(p) = 6p− p 3 −2$
Try It #3

Identify the degree, leading term, and leading coefficient of the polynomial$f(x)=4 x 2 − x 6 +2x−6. f(x)=4 x 2 − x 6 +2x−6.$

#### Identifying End Behavior of Polynomial Functions

Knowing the degree of a polynomial function is useful in helping us predict its end behavior. To determine its end behavior, look at the leading term of the polynomial function. Because the power of the leading term is the highest, that term will grow significantly faster than the other terms as$x x$ gets very large or very small, so its behavior will dominate the graph. For any polynomial, the end behavior of the polynomial will match the end behavior of the power function consisting of the leading term. See Table 3.

Polynomial Function Leading Term Graph of Polynomial Function
$f(x)=5 x 4 +2 x 3 −x−4 f(x)=5 x 4 +2 x 3 −x−4$ $5 x 4 5 x 4$
$f(x)=−2 x 6 − x 5 +3 x 4 + x 3 f(x)=−2 x 6 − x 5 +3 x 4 + x 3$ $−2 x 6 −2 x 6$
$f(x)=3 x 5 −4 x 4 +2 x 2 +1 f(x)=3 x 5 −4 x 4 +2 x 2 +1$ $3 x 5 3 x 5$
$f(x)=−6 x 3 +7 x 2 +3x+1 f(x)=−6 x 3 +7 x 2 +3x+1$ $−6 x 3 −6 x 3$
Table 3

### Example 6

#### Identifying End Behavior and Degree of a Polynomial Function

Describe the end behavior and determine a possible degree of the polynomial function in Figure 7.

Figure 7

### Try It #4

Describe the end behavior, and determine a possible degree of the polynomial function in Figure 8.

Figure 8

### Example 7

#### Identifying End Behavior and Degree of a Polynomial Function

Given the function$f(x)=−3 x 2 (x−1)(x+4), f(x)=−3 x 2 (x−1)(x+4),$express the function as a polynomial in general form, and determine the leading term, degree, and end behavior of the function.

### Try It #5

Given the function$f(x)=0.2(x−2)(x+1)(x−5), f(x)=0.2(x−2)(x+1)(x−5),$express the function as a polynomial in general form and determine the leading term, degree, and end behavior of the function.

#### Identifying Local Behavior of Polynomial Functions

In addition to the end behavior of polynomial functions, we are also interested in what happens in the “middle” of the function. In particular, we are interested in locations where graph behavior changes. A turning point is a point at which the function values change from increasing to decreasing or decreasing to increasing.

We are also interested in the intercepts. As with all functions, the y-intercept is the point at which the graph intersects the vertical axis. The point corresponds to the coordinate pair in which the input value is zero. Because a polynomial is a function, only one output value corresponds to each input value so there can be only one y-intercept$(0, a 0 ). (0, a 0 ).$The x-intercepts occur at the input values that correspond to an output value of zero. It is possible to have more than one x-intercept. See Figure 9.

Figure 9

### Intercepts and Turning Points of Polynomial Functions

A turning point of a graph is a point at which the graph changes direction from increasing to decreasing or decreasing to increasing. The y-intercept is the point at which the function has an input value of zero. The x-intercepts are the points at which the output value is zero.

### How To

Given a polynomial function, determine the intercepts.

1. Determine the y-intercept by setting $x=0 x=0$ and finding the corresponding output value.
2. Determine the x-intercepts by solving for the input values that yield an output value of zero.

### Example 8

#### Determining the Intercepts of a Polynomial Function

Given the polynomial function$f(x)=(x−2)(x+1)(x−4), f(x)=(x−2)(x+1)(x−4),$written in factored form for your convenience, determine the y- and x-intercepts.

### Example 9

#### Determining the Intercepts of a Polynomial Function with Factoring

Given the polynomial function$f(x)= x 4 −4 x 2 −45, f(x)= x 4 −4 x 2 −45,$determine the y- and x-intercepts.

### Try It #6

Given the polynomial function$f(x)=2 x 3 −6 x 2 −20x, f(x)=2 x 3 −6 x 2 −20x,$determine the y- and x-intercepts.

#### Comparing Smooth and Continuous Graphs

The degree of a polynomial function helps us to determine the number of x-intercepts and the number of turning points. A polynomial function of$nth nth$degree is the product of$n n$factors, so it will have at most$n n$roots or zeros, or x-intercepts. The graph of the polynomial function of degree$n n$must have at most$n–1 n–1$turning points. This means the graph has at most one fewer turning point than the degree of the polynomial or one fewer than the number of factors.

A continuous function has no breaks in its graph: the graph can be drawn without lifting the pen from the paper. A smooth curve is a graph that has no sharp corners. The turning points of a smooth graph must always occur at rounded curves. The graphs of polynomial functions are both continuous and smooth.

### Intercepts and Turning Points of Polynomials

A polynomial of degree$n n$will have, at most,$n n$x-intercepts and$n−1 n−1$turning points.

### Example 10

#### Determining the Number of Intercepts and Turning Points of a Polynomial

Without graphing the function, determine the local behavior of the function by finding the maximum number of x-intercepts and turning points for$f(x)=−3 x 10 +4 x 7 − x 4 +2 x 3 . f(x)=−3 x 10 +4 x 7 − x 4 +2 x 3 .$

### Try It #7

Without graphing the function, determine the maximum number of x-intercepts and turning points for$f(x)=108−13 x 9 −8 x 4 +14 x 12 +2 x 3 . f(x)=108−13 x 9 −8 x 4 +14 x 12 +2 x 3 .$

### Example 11

#### Drawing Conclusions about a Polynomial Function from the Graph

What can we conclude about the polynomial represented by the graph shown in Figure 12 based on its intercepts and turning points?

Figure 12

### Try It #8

What can we conclude about the polynomial represented by the graph shown in Figure 14 based on its intercepts and turning points?

Figure 14

### Example 12

#### Drawing Conclusions about a Polynomial Function from the Factors

Given the function$f(x)=−4x( x+3 )( x−4 ), f(x)=−4x( x+3 )( x−4 ),$ determine the local behavior.

### Try It #9

Given the function$f(x)=0.2(x−2)(x+1)(x−5), f(x)=0.2(x−2)(x+1)(x−5),$determine the local behavior.

### Media

Access these online resources for additional instruction and practice with power and polynomial functions.

### 5.2 Section Exercises

#### Verbal

1.

Explain the difference between the coefficient of a power function and its degree.

2.

If a polynomial function is in factored form, what would be a good first step in order to determine the degree of the function?

3.

In general, explain the end behavior of a power function with odd degree if the leading coefficient is positive.

4.

What is the relationship between the degree of a polynomial function and the maximum number of turning points in its graph?

5.

What can we conclude if, in general, the graph of a polynomial function exhibits the following end behavior? As$x→−∞, f(x)→−∞ x→−∞, f(x)→−∞$ and as$x→∞, f(x)→−∞. x→∞, f(x)→−∞.$

#### Algebraic

For the following exercises, identify the function as a power function, a polynomial function, or neither.

6.

$f(x)= x 5 f(x)= x 5$

7.

$f(x)= ( x 2 ) 3 f(x)= ( x 2 ) 3$

8.

$f(x)=x− x 4 f(x)=x− x 4$

9.

$f(x)= x 2 x 2 −1 f(x)= x 2 x 2 −1$

10.

$f(x)=2x( x+2 ) ( x−1 ) 2 f(x)=2x( x+2 ) ( x−1 ) 2$

11.

$f(x)= 3 x+1 f(x)= 3 x+1$

For the following exercises, find the degree and leading coefficient for the given polynomial.

12.

$−3x 4 −3x 4$

13.

$7−2 x 2 7−2 x 2$

14.

15.

$x( 4− x 2 )(2x+1) x( 4− x 2 )(2x+1)$

16.

$x 2 ( 2x−3 ) 2 x 2 ( 2x−3 ) 2$

For the following exercises, determine the end behavior of the functions.

17.

$f( x )= x 4 f( x )= x 4$

18.

$f( x )= x 3 f( x )= x 3$

19.

$f( x )=− x 4 f( x )=− x 4$

20.

$f( x )=− x 9 f( x )=− x 9$

21.

22.

$f(x)=3 x 2 +x−2 f(x)=3 x 2 +x−2$

23.

$f(x)= x 2 ( 2 x 3 −x+1 ) f(x)= x 2 ( 2 x 3 −x+1 )$

24.

$f(x)= (2−x) 7 f(x)= (2−x) 7$

For the following exercises, find the intercepts of the functions.

25.

$f( t )=2( t−1 )( t+2 )(t−3) f( t )=2( t−1 )( t+2 )(t−3)$

26.

$g( n )=−2( 3n−1 )(2n+1) g( n )=−2( 3n−1 )(2n+1)$

27.

$f(x)= x 4 −16 f(x)= x 4 −16$

28.

$f(x)= x 3 +27 f(x)= x 3 +27$

29.

$f(x)=x( x 2 −2x−8 ) f(x)=x( x 2 −2x−8 )$

30.

$f(x)=(x+3)( 4 x 2 −1 ) f(x)=(x+3)( 4 x 2 −1 )$

#### Graphical

For the following exercises, determine the least possible degree of the polynomial function shown.

31.
32.
33.
34.
35.
36.
37.
38.

For the following exercises, determine whether the graph of the function provided is a graph of a polynomial function. If so, determine the number of turning points and the least possible degree for the function.

39.
40.
41.
42.
43.
44.
45.

#### Numeric

For the following exercises, make a table to confirm the end behavior of the function.

46.

$f(x)=− x 3 f(x)=− x 3$

47.

$f(x)= x 4 −5 x 2 f(x)= x 4 −5 x 2$

48.

$f(x)= x 2 ( 1−x ) 2 f(x)= x 2 ( 1−x ) 2$

49.

$f(x)=(x−1)(x−2)(3−x) f(x)=(x−1)(x−2)(3−x)$

50.

$f(x)= x 5 10 − x 4 f(x)= x 5 10 − x 4$

#### Technology

For the following exercises, graph the polynomial functions using a calculator. Based on the graph, determine the intercepts and the end behavior.

51.

$f(x)= x 3 (x−2) f(x)= x 3 (x−2)$

52.

$f(x)=x(x−3)(x+3) f(x)=x(x−3)(x+3)$

53.

$f(x)=x(14−2x)(10−2x) f(x)=x(14−2x)(10−2x)$

54.

$f(x)=x(14−2x) (10−2x) 2 f(x)=x(14−2x) (10−2x) 2$

55.

$f(x)= x 3 −16x f(x)= x 3 −16x$

56.

$f(x)= x 3 −27 f(x)= x 3 −27$

57.

$f(x)= x 4 −81 f(x)= x 4 −81$

58.

$f(x)=− x 3 + x 2 +2x f(x)=− x 3 + x 2 +2x$

59.

$f(x)= x 3 −2 x 2 −15x f(x)= x 3 −2 x 2 −15x$

60.

$f(x)= x 3 −0.01x f(x)= x 3 −0.01x$

#### Extensions

For the following exercises, use the information about the graph of a polynomial function to determine the function. Assume the leading coefficient is 1 or –1. There may be more than one correct answer.

61.

The$y- y-$intercept is$(0,−4). (0,−4).$The$x- x-$intercepts are$(−2,0), (2,0). (−2,0), (2,0).$Degree is 2.

End behavior:$as x→−∞, f(x)→∞, as x→∞, f(x)→∞. as x→−∞, f(x)→∞, as x→∞, f(x)→∞.$

62.

The$y- y-$intercept is$(0,9). (0,9).$The$x- x-$intercepts are$(−3,0), (3,0). (−3,0), (3,0).$Degree is 2.

End behavior:$as x→−∞, f(x)→−∞, as x→∞, f(x)→−∞. as x→−∞, f(x)→−∞, as x→∞, f(x)→−∞.$

63.

The$y- y-$intercept is$(0,0). (0,0).$The$x- x-$intercepts are$(0,0), (2,0). (0,0), (2,0).$Degree is 3.

End behavior:$as x→−∞, f(x)→−∞, as x→∞, f(x)→∞. as x→−∞, f(x)→−∞, as x→∞, f(x)→∞.$

64.

The$y- y-$intercept is$(0,1). (0,1).$The$x- x-$intercept is$(1,0). (1,0).$Degree is 3.

End behavior:$as x→−∞, f(x)→∞, as x→∞, f(x)→−∞. as x→−∞, f(x)→∞, as x→∞, f(x)→−∞.$

65.

The$y- y-$intercept is$(0,1). (0,1).$There is no$x- x-$intercept. Degree is 4.

End behavior:$as x→−∞, f(x)→∞, as x→∞, f(x)→∞. as x→−∞, f(x)→∞, as x→∞, f(x)→∞.$

#### Real-World Applications

For the following exercises, use the written statements to construct a polynomial function that represents the required information.

66.

An oil slick is expanding as a circle. The radius of the circle is increasing at the rate of 20 meters per day. Express the area of the circle as a function of$d, d,$the number of days elapsed.

67.

A cube has an edge of 3 feet. The edge is increasing at the rate of 2 feet per minute. Express the volume of the cube as a function of$m, m,$the number of minutes elapsed.

68.

A rectangle has a length of 10 inches and a width of 6 inches. If the length is increased by$x x$inches and the width increased by twice that amount, express the area of the rectangle as a function of$x. x.$

69.

An open box is to be constructed by cutting out square corners of $x- x-$inch sides from a piece of cardboard 8 inches by 8 inches and then folding up the sides. Express the volume of the box as a function of$x. x.$

70.

A rectangle is twice as long as it is wide. Squares of side 2 feet are cut out from each corner. Then the sides are folded up to make an open box. Express the volume of the box as a function of the width ($x x$).


text:
Logical Options, 1

As I noted in my last post, I’m going to be working through Bell, DeVidi and Solomon’s Logical Options in a seminar with some second year undergrads this coming term. To answer Richard Zach’s question, I might have used Ted Sider’s draft book as the main text if I’d known about it before plans were made in November — though Logical Options does still perhaps more neatly dovetail with our tree-based first year course.

Because the seminar starts on the first teaching day of term, I can’t presume much reading. So we’ll have to make a slow start. Here though are the reading notes for the first session, in case anyone else is interested. (It goes without saying that corrections and/or suggestions are always welcome!)

This entry was posted in This and that. Bookmark the permalink.


text:
Waiting for answer This question has not been answered yet. You can hire a professional tutor to get the answer.

QUESTION

# What is the net ionic equation of the reaction of MgSO4 with Pb(NO3)2?

SO_(4(aq))^(2-) + Pb_((aq))^(2+) -> PbSO_(4(s))

The balanced equation for this reaction is

MgSO_(4(aq)) + Pb(NO_3)_(2(aq)) ->Mg(NO_3)_2(aq) + PbSO_4(s)

The complete ionic equation is

Mg_((aq))^(2+) + SO_(4(aq))^(2-) + Pb_((aq))^(2+) + 2NO_(3(aq))^(-) -> PbSO_(4(s)) + Mg_((aq))^(2+) + + 2NO_(3(aq))^(-)

If you eliminate spectator ions, which are the ions thatcan be found both on the reactants' and on the products' side, you'll get the net ionic equation

SO_(4(aq))^(2-) + Pb_((aq))^(2+) -> PbSO_(4(s))

Lead (II) sulfate is insoluble in aqueous solution and will form a precipitate.

Here is another example which illustrates how to write a net ionic equation. video from: Noel Pauller


text:
# zbMATH — the first resource for mathematics

A Banach-Stone theorem for Riesz isomorphisms of Banach lattices. (English) Zbl 1160.46026
Summary: Let $$X$$ and $$Y$$ be compact Hausdorff spaces and $$E, F$$ be Banach lattices. Let $$C(X,E)$$ denote the Banach lattice of all continuous $$E$$-valued functions on $$X$$ equipped with the pointwise ordering and the sup norm. We prove that, if there exists a Riesz isomorphism $$\Phi: C(X,E)\rightarrow C(Y,F)$$ such that $$\Phi f$$ is non-vanishing on $$Y$$ if and only if $$f$$ is non-vanishing on $$X$$, then $$X$$ is homeomorphic to $$Y$$, and $$E$$ is Riesz isomorphic to $$F$$. In this case, $$\Phi$$ can be written as a weighted composition operator: $$\Phi f(y)=\Pi(y)(f(\varphi(y)))$$, where $$\varphi$$ is a homeomorphism from $$Y$$ onto $$X$$, and $$\Pi(y)$$ is a Riesz isomorphism from $$E$$ onto $$F$$ for every $$y$$ in $$Y$$. This generalizes some known results obtained recently.

##### MSC:
 46E40 Spaces of vector- and operator-valued functions 46B42 Banach lattices 47B65 Positive linear operators and order-bounded operators
Full Text:
##### References:
 [1] Y. A. Abramovich and C. D. Aliprantis, An invitation to operator theory, Graduate Studies in Mathematics, vol. 50, American Mathematical Society, Providence, RI, 2002. · Zbl 1022.47001 [2] Charalambos D. Aliprantis and Owen Burkinshaw, Positive operators, Pure and Applied Mathematics, vol. 119, Academic Press, Inc., Orlando, FL, 1985. · Zbl 0608.47039 [3] Ehrhard Behrends, How to obtain vector-valued Banach-Stone theorems by using \?-structure methods, Math. Ann. 261 (1982), no. 3, 387 – 398. · Zbl 0511.46034 [4] Ehrhard Behrends and Michael Cambern, An isomorphic Banach-Stone theorem, Studia Math. 90 (1988), no. 1, 15 – 26. · Zbl 0664.46036 [5] J. Cao, I. Reilly, and H. Xiong, A lattice-valued Banach-Stone theorem, Acta Math. Hungar. 98 (2003), no. 1-2, 103 – 110. · Zbl 1027.46025 [6] John B. Conway, A course in functional analysis, 2nd ed., Graduate Texts in Mathematics, vol. 96, Springer-Verlag, New York, 1990. · Zbl 0706.46003 [7] Z. Ercan and S. Önal, Banach-Stone theorem for Banach lattice valued continuous functions, Proc. Amer. Math. Soc. 135 (2007), no. 9, 2827 – 2829. · Zbl 1127.46026 [8] Marián Fabian, Petr Habala, Petr Hájek, Vicente Montesinos Santalucía, Jan Pelant, and Václav Zizler, Functional analysis and infinite-dimensional geometry, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 8, Springer-Verlag, New York, 2001. · Zbl 0981.46001 [9] Hwa-Long Gau, Jyh-Shyang Jeang, and Ngai-Ching Wong, Biseparating linear maps between continuous vector-valued function spaces, J. Aust. Math. Soc. 74 (2003), no. 1, 101 – 109. · Zbl 1052.47017 [10] S. Hernandez, E. Beckenstein, and L. Narici, Banach-Stone theorems and separating maps, Manuscripta Math. 86 (1995), no. 4, 409 – 416. · Zbl 0827.46032 [11] W. Holsztyński, Continuous mappings induced by isometries of spaces of continuous function, Studia Math. 26 (1966), 133 – 136. · Zbl 0156.36903 [12] Jyh-Shyang Jeang and Ngai-Ching Wong, On the Banach-Stone problem, Studia Math. 155 (2003), no. 2, 95 – 105. · Zbl 1056.46011 [13] M. Jerison, The space of bounded maps into a Banach space, Ann. of Math.(2) 52 (1950), 309-327. · Zbl 0038.27301 [14] E. de Jonge and A. C. M. van Rooij, Introduction to Riesz spaces, Mathematisch Centrum, Amsterdam, 1977. Mathematical Centre Tracts, No. 78. · Zbl 0421.46001 [15] Jung-Hui Liu and Ngai-Ching Wong, Local automorphisms of operator algebras, Taiwanese J. Math. 11 (2007), no. 3, 611 – 619. · Zbl 1147.46038 [16] Xinhe Miao, Jiling Cao, and Hongyun Xiong, Banach-Stone theorems and Riesz algebras, J. Math. Anal. Appl. 313 (2006), no. 1, 177 – 183. · Zbl 1102.46017
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:
Fast Fourier transform

In this article we will discuss an algorithm that allows us to multiply two polynomials of length $n$ in $O(n \log n)$ time, which is better than the trivial multiplication which takes $O(n^2)$ time. Obviously also multiplying two long numbers can be reduced to multiplying polynomials, so also two long numbers can be multiplied in $O(n \log n)$ time (where $n$ is the number of digits in the numbers).

The discovery of the Fast Fourier transformation (FFT) is attributed to Cooley and Tukey, who published an algorithm in 1965. But in fact the FFT has been discovered repeatedly before, but the importance of it was not understood before the inventions of modern computers. Some researchers attribute the discovery of the FFT to Runge and König in 1924. But actually Gauss developed such a method already in 1805, but never published it.

Discrete Fourier transform

Let there be a polynomial of degree $n - 1$: $$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}$$ Without loss of generality we assume that $n$ - the number of coefficients - is a power of $2$. If $n$ is not a power of $2$, then we simply add the missing terms $a_i x^i$ and set the coefficients $a_i$ to $0$.

The theory of complex numbers tells us that the equation $x^n = 1$ has $n$ complex solutions (called the $n$-th roots of unity), and the solutions are of the form $w_{n, k} = e^{\frac{2 k \pi i}{n}}$ with $k = 0 \dots n-1$. Additionally these complex numbers have some very interesting properties: e.g. the principal $n$-th root $w_n = w_{n, 1} = e^{\frac{2 \pi i}{n}}$ can be used to describe all other $n$-th roots: $w_{n, k} = (w_n)^k$.

The discrete Fourier transform (DFT) of the polynomial $A(x)$ (or equivalently the vector of coefficients $(a_0, a_1, \dots, a_{n-1})$ is defined as the values of the polynomial at the points $x = w_{n, k}$, i.e. it is the vector: \begin{align} \text{DFT}(a_0, a_1, \dots, a_{n-1}) &= (y_0, y_1, \dots, y_{n-1}) \\ &= (A(w_{n_0}), A(w_{n, 1}), \dots, A(w_{n, n-1})) \\ &= (A(w_n^0), A(w_n^1), \dots, A(w_n^{n-1})) \end{align}

Similarly the inverse discrete Fourier transform is defined: The inverse DFT of values of the polynomial $(y_0, y_1, \dots, y_{n-1})$ are the coefficients of the polynomial $(a_0, a_1, \dots, a_{n-1})$. $$\text{InverseDFT}(y_0, y_1, \dots, y_{n-1}) = (a_0, a_1, \dots, a_{n-1})$$

Thus, if a direct DFT computes the values of the polynomial at the points at the $n$-th roots, the inverse DFT can restore the coefficients of the polynomial using those values.

Application of the DFT: fast multiplication of polynomials

Let there be two polynomials $A$ and $B$. We compute the DFT for each of them: $\text{DFT}(A)$ and $\text{DFT}(B)$.

What happens if we multiply these polynomials? Obviously at each point the values are simply multiplied, i.e. $$(A \cdot B)(x) = A(x) \cdot B(x).$$

This means that if we multiply the vectors $\text{DFT}(A)$ and $\text{DFT}(B)$ - by multiplying each element of one vector by the corresponding element of the other vector - then we get nothing other than the DFT of the polynomial $\text{DFT}(A \cdot B)$: $$\text{DFT}(A \cdot B) = \text{DFT}(A) \cdot \text{DFT}(B)$$

Finally, applying the inverse DFT, we obtain: $$A \cdot B = \text{InverseDFT}(\text{DFT}(A) \cdot \text{DFT}(B))$$

On the right the product of the two DFTs we mean the pairwise product of the vector elements. This can be computed in $O(n)$ time. If we can compute the DFT and the inverse DFT in $O(n \log n)$, then we can compute the product of the two polynomials (and consequently also two long numbers) with the same time complexity.

It should be noted, that the two polynomials should have the same degree. Otherwise the two result vectors of the DFT have different length. We can accomplish this by adding coefficients with the value $0$.

And also, since the result of the product of two polynomials is a polynomial of degree $2 (n - 1)$, we have to double the degrees of each polynomial (again by padding $0$s). From a vector with $n$ values we cannot reconstruct the desired polynomial with $2n - 1$ coefficients.

Fast Fourier Transform

The fast Fourier transform is a method that allows computing the DFT in $O(n \log n)$ time. The basic idea of the FFT is to apply divide and conquer. We divide the coefficient vector of the polynomial into two vectors, recursively compute the DFT for each of them, and combine the results to compute the DFT of the complete polynomial.

So let there be a polynomial $A(x)$ with degree $n - 1$, where $n$ is a power of $2$, and $n > 1$: $$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}$$

We divide it into two smaller polynomials, the one containing only the coefficients of the even positions, and the one containing the coefficients of the odd positions: \begin{align} A_0(x) &= a_0 x^0 + a_2 x^1 + \dots + a_{n-2} x^{\frac{n}{2}-1} \\ A_1(x) &= a_1 x^0 + a_3 x^1 + \dots + a_{n-1} x^{\frac{n}{2}-1} \end{align}

It is easy to see that $$A(x) = A_0(x^2) + x A_1(x^2).$$

The polynomials $A_0$ and $A_1$ are only half as much coefficients as the polynomial $A$. If we can compute the $\text{DFT}(A)$ in linear time using $\text{DFT}(A_0)$ and $\text{DFT}(A_1)$, then we get the recurrence $T_{\text{DFT}}(n) = 2 T_{\text{DFT}}\left(\frac{n}{2}\right) + O(n)$ for the time complexity, which results in $T_{\text{DFT}}(n) = O(n \log n)$ by the master theorem.

Let's learn how we can accomplish that.

Suppose we have computed the vectors $\left(y_k^0\right)_{k=0}^{n/2-1} = \text{DFT}(A_0)$ and $\left(y_k^1\right)_{k=0}^{n/2-1} = \text{DFT}(A_1)$. Let us find a expression for $\left(y_k\right)_{k=0}^{n-1} = \text{DFT}(A)$.

For the first $\frac{n}{2}$ values we can just use the previously noted equation $A(x) = A_0(x^2) + x A_1(x^2)$: $$y_k = y_k^0 + w_n^k y_k^1, \quad k = 0 \dots \frac{n}{2} - 1.$$

However for the second $\frac{n}{2}$ values we need to find a slightly, different expression: \begin{align} y_{k+n/2} &= A\left(w_n^{k+n/2}\right) \\ &= A_0\left(w_n^{2k+n}\right) + w_n^{k + n/2} A_1\left(w_n^{2k+n}\right) \\ &= A_0\left(w_n^{2k} w_n^n\right) + w_n^k w_n^{n/2} A_1\left(w_n^{2k} w_n^n\right) \\ &= A_0\left(w_n^{2k}\right) - w_n^k A_1\left(w_n^{2k}\right) \\ &= y_k^0 - w_n^k y_k^1 \end{align} Here we used again $A(x) = A_0(x^2) + x A_1(x^2)$ and the two identities $w_n^n = 1$ and $w_n^{n/2} = -1$.

Therefore we get the desired formulas for computing the whole vector $(y_k)$: \begin{align} y_k &= y_k^0 + w_n^k y_k^1, &\quad k = 0 \dots \frac{n}{2} - 1, \\ y_{k+n/2} &= y_k^0 - w_n^k y_k^1, &\quad k = 0 \dots \frac{n}{2} - 1. \end{align} (This pattern $a + b$ and $a - b$ is sometimes called a butterfly.)

Thus we learned how to compute the DFT in $O(n \log n)$ time.

Inverse FFT

Let the vector $(y_0, y_1, \dots y_{n-1})$ - the values of polynomial $A$ of degree $n - 1$ in the points $x = w_n^k$ - be given. We want to restore the coefficients $(a_0, a_1, \dots, a_{n-1})$ of the polynomial. This known problem is called interpolation, and there are general algorithms for solving it. But in this special case (since we know the values of the points at the roots of unity), we can obtains a much simpler algorithm (that is practically the same as the direct FFT).

We can write the DFT, according to its definition, in the matrix form: $$\begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^1 & w_n^2 & w_n^3 & \cdots & w_n^{n-1} \\ w_n^0 & w_n^2 & w_n^4 & w_n^6 & \cdots & w_n^{2(n-1)} \\ w_n^0 & w_n^3 & w_n^6 & w_n^9 & \cdots & w_n^{3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{n-1} & w_n^{2(n-1)} & w_n^{3(n-1)} & \cdots & w_n^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{n-1} \end{pmatrix}$$ This matrix is called the Vandermonde matrix.

Thus we can compute the vector $(a_0, a_1, \dots, a_{n-1})$ by multiplying the vector $(y_0, y_1, \dots y_{n-1})$ from the left with the inverse of the matrix: $$\begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^1 & w_n^2 & w_n^3 & \cdots & w_n^{n-1} \\ w_n^0 & w_n^2 & w_n^4 & w_n^6 & \cdots & w_n^{2(n-1)} \\ w_n^0 & w_n^3 & w_n^6 & w_n^9 & \cdots & w_n^{3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{n-1} & w_n^{2(n-1)} & w_n^{3(n-1)} & \cdots & w_n^{(n-1)(n-1)} \end{pmatrix}^{-1} \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{n-1} \end{pmatrix}$$

A quick check can verify that the inverse of the matrix has the following form: $$\frac{1}{n} \begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^{-1} & w_n^{-2} & w_n^{-3} & \cdots & w_n^{-(n-1)} \\ w_n^0 & w_n^{-2} & w_n^{-4} & w_n^{-6} & \cdots & w_n^{-2(n-1)} \\ w_n^0 & w_n^{-3} & w_n^{-6} & w_n^{-9} & \cdots & w_n^{-3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{-(n-1)} & w_n^{-2(n-1)} & w_n^{-3(n-1)} & \cdots & w_n^{-(n-1)(n-1)} \end{pmatrix}$$ Thus we obtain the formula: $$a_k = \frac{1}{n} \sum_{j=0}^{n-1} y_j w_n^{-k j}$$ Comparing this to the formula for $y_k$ $$y_k = \sum_{j=0}^{n-1} a_j w_n^{k j},$$ we notice that these problems are almost the same, so the coefficients $a_k$ can be found by the same divide and conquer algorithm, as well as the direct FFT, only instead of $w_n^k$ we have to use $w_n^{-k}$, and at the end we need to divide the resulting coefficients by $n$.

Thus the computation of the inverse DFT is almost the same as the calculation of the direct DFT, and it also can be performed in $O(n \log n)$ time.

Implementation

Here we present a simple recursive implementation of the FFT and the inverse FFT, both in one function, since the difference between the forward and the inverse FFT are so minimal. To store the complex numbers we use the complex type in the C++ STL.

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
int n = a.size();
if (n == 1)
return;

vector<cd> a0(n / 2), a1(n / 2);
for (int i = 0; 2 * i < n; i++) {
a0[i] = a[2*i];
a1[i] = a[2*i+1];
}
fft(a0, invert);
fft(a1, invert);

double ang = 2 * PI / n * (invert ? -1 : 1);
cd w(1), wn(cos(ang), sin(ang));
for (int i = 0; 2 * i < n; i++) {
a[i] = a0[i] + w * a1[i];
a[i + n/2] = a0[i] - w * a1[i];
if (invert) {
a[i] /= 2;
a[i + n/2] /= 2;
}
w *= wn;
}
}

The function gets passed a vector of coefficients, and the function will compute the DFT or inverse DFT and store the result again in this vector. The argument $\text{invert}$ shows whether the direct or the inverse DFT should be computed. Inside the function we first check if the length of the vector is equal to one, if this is the case then we don't have to do anything. Otherwise we divide the vector $a$ into two vectors $a0$ and $a1$ and compute the DFT for both recursively. Then we initialize the value $wn$ and a variable $w$, which will contain the current power of $wn$. Then the values of the resulting DFT are computed using the above formulas.

If the flag $\text{invert}$ is set, then we replace $wn$ with $wn^{-1}$, and each of the values of the result is divided by $2$ (since this will be done in each level of the recursion, this will end up dividing the final values by $n$).

Using this function we can create a function for multiplying two polynomials:

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size())
n <<= 1;
fa.resize(n);
fb.resize(n);

fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);

vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}

This function works with polynomials with integer coefficients, however you can also adjust it to work with other types. Since there is some error when working with complex numbers, we need round the resulting coefficients at the end.

Finally the function for multiplying two long numbers practically doesn't differ from the function for multiplying polynomials. The only thing we have to do afterwards, is to normalize the number:

    int carry = 0;
for (int i = 0; i < n; i++)
result[i] += carry;
carry = result[i] / 10;
result[i] %= 10;
}

Since the length of the product of two numbers never exceed the total length of both numbers, the size of the vector is enough to perform all carry operations.

Improved implementation: in-place computation

To increase the efficiency we will switch from the recursive implementation to an iterative one. In the above recursive implementation we explicitly separated the vector $a$ into two vectors - the element on the even positions got assigned to one temporary vector, and the elements on odd positions to another. However if we reorder the elements in a certain way, we don't need to create these temporary vectors (i.e. all the calculations can be done "in-place", right in the vector $A$ itself).

Note that at the first recursion level, the elements whose lowest bit of the position was zero got assigned to the vector $a_0$, and the ones with a one as the lowest bit of the position got assigned to $a_1$. In the second recursion level the same thing happens, but with the second lowest bit instead, etc. Therefore if we reverse the bits of the position of each coefficient, and sort them by these reversed values, we get the desired order (it is called the bit-reversal permutation).

For example the desired order for $n = 8$ has the form: $$a = \left\{ \left[ (a_0, a_4), (a_2, a_6) \right], \left[ (a_1, a_5), (a_3, a_7) \right] \right\}$$ Indeed in the first recursion level (surrounded by curly braces), the vector gets divided into two parts $[a_0, a_2, a_4, a_6]$ and $[a_1, a_3, a_5, a_7]$. As we see, in the bit-reversal permutation this corresponds to simply dividing the vector into two halves: the first $\frac{n}{2}$ elements and the last $\frac{n}{2}$ elements. Then there is a recursive call for each halve. Let the resulting DFT for each of them be returned in place of the elements themselves (i.e. the first half and the second half of the vector $a$ respectively. $$a = \left\{[y_0^0, y_1^0, y_2^0, y_3^0], [y_0^1, y_1^1, y_2^1, y_3^1]\right\}$$

Now we want to combine the two DFTs into one for the complete vector. The order of the elements is ideal, and we can also perform the union directly in this vector. We can take the elements $y_0^0$ and $y_0^1$ and perform the butterfly transform. The place of the resulting two values is the same as the place of the two initial values, so we get: $$a = \left\{[y_0^0 + w_n^0 y_0^1, y_1^0, y_2^0, y_3^0], [y_0^0 - w_n^0 y_0^1, y_1^1, y_2^1, y_3^1]\right\}$$ Similarly we can compute the butterfly transform of $y_1^0$ and $y_1^1$ and put the results in their place, and so on. As a result we get: $$a = \left\{[y_0^0 + w_n^0 y_0^1, y_1^0 + w_n^1 y_1^1, y_2^0 + w_n^2 y_2^1, y_3^0 + w_n^3 y_3^1], [y_0^0 - w_n^0 y_0^1, y_1^0 - w_n^1 y_1^1, y_2^0 - w_n^2 y_2^1, y_3^0 - w_n^3 y_3^1]\right\}$$ Thus we computed the required DFT from the vector $a$.

Here we described the process of computing the DFT only at the first recursion level, but the same works obviously also for all other levels. Thus, after applying the bit-reversal permutation, we can compute the DFT in-place, without any additional memory.

This additionally allows us to get rid of the recursion. We just start at the lowest level, i.e. we divide the vector into pairs and apply the butterfly transform to them. This results with the vector $a$ with the work of the last level applied. In the next step we divide the vector into vectors of size $4$, and again apply the butterfly transform, which gives us the DFT for each block of size $4$. And so on. Finally in the last step we obtained the result of the DFTs of both halves of $a$, and by applying the butterfly transform we obtain the DFT for the complete vector $a$.

using cd = complex<double>;
const double PI = acos(-1);

int reverse(int num, int lg_n) {
int res = 0;
for (int i = 0; i < lg_n; i++) {
if (num & (1 << i))
res |= 1 << (lg_n - 1 - i);
}
return res;
}

void fft(vector<cd> & a, bool invert) {
int n = a.size();
int lg_n = 0;
while ((1 << lg_n) < n)
lg_n++;

for (int i = 0; i < n; i++) {
if (i < reverse(i, lg_n))
swap(a[i], a[reverse(i, lg_n)]);
}

for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}

if (invert) {
for (cd & x : a)
x /= n;
}
}

At first we apply the bit-reversal permutation by swapping the each element with the element of the reversed position. Then the $\log n - 1$ states of the algorithm we compute the DFT for each block of the corresponding size $\text{len}$. For all those blocks we have the same root of unity $\text{wlen}$. We iterate all blocks and perform the butterfly transform on each of them.

We can further optimize the reversal of the bits. In the previous implementation we iterated all bits of the index and created the bitwise reversed index. However we can reverse the bits in a different way.

Suppose that $j$ already contains the reverse of $i$. Then by to go to $i + 1$, we have to increment $i$, and we also have to increment $j$, but in a "reversed" number system. Adding one in the conventional binary system is equivalent to flip all tailing ones into zeros and flipping the zero right before them into a one. Equivalently in the "reversed" number system, we flip all leading ones, and the also the next zero.

Thus we get the following implementation:

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
int n = a.size();

for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;

if (i < j)
swap(a[i], a[j]);
}

for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}

if (invert) {
for (cd & x : a)
x /= n;
}
}

Additionally we can precompute the bit-reversal permutation beforehand. This is especially useful when the size $n$ is the same for all calls. But even when we only have three calls (which are necessary for multiplying two polynomials), the effect is noticeable. Also we can precompute all roots of unity and their powers.

Number theoretic transform

Now we switch the objective a little bit. We still want to multiply two polynomials in $O(n \log n)$ time, but this time we want to compute the coefficients modulo some prime number $p$. Of course for this task we can use the normal DFT and apply the modulo operator to the result. However, doing so might lead to rounding errors, especially when dealing with large numbers. The number theoretic transform (NTT) has the advantage, that it only works with integer, and therefore the result are guaranteed to be correct.

The discrete Fourier transform is based on complex numbers, and the $n$-th roots of unity. To efficiently compute it, we extensively use properties of the roots (e.g. that there is one root that generates all other roots by exponentiation).

But the same properties hold for the $n$-th roots of unity in modular arithmetic. A $n$-th root of unity under a primitive field is such a number $w_n$ that satisfies: \begin{align} (w_n)^n &= 1 \pmod{p}, \\ (w_n)^k &\ne 1 \pmod{p}, \quad 1 \le k < n. \end{align} The other $n-1$ roots can be obtained as powers of the root $w_n$.

To apply it in the fast Fourier transform algorithm, we need a root to exist for some $n$, which is a power of $2$, and also for all smaller powers. We can notice the following interesting property: \begin{align} (w_n^2)^m = w_n^n &= 1 \pmod{p}, \quad \text{with } m = \frac{n}{2}\\ (w_n^2)^k = w_n^{2k} &\ne 1 \pmod{p}, \quad 1 \le k < m. \end{align} Thus if $w_n$ is a $n$-th root of unity, then $w_n^2$ is a $\frac{n}{2}$-th root of unity. And consequently for all smaller powers of two there exist roots of the required degree, and they can be computed using $w_n$.

For computing the inverse DFT, we need the inverse $w_n^{-1}$ of $w_n$. But for a prime modulus the inverse always exists.

Thus all the properties that we need from the complex roots are also available in modular arithmetic, provided that we have a large enough module $p$ for which a $n$-th root of unity exists.

For example we can take the following values: module $p = 7340033$, $w_{2^{20}} = 5$. If this module is not enough, we need to find a different pair. We can use that fact that for modules of the form $p = c 2^k + 1$ (and $p$ is prime), there always exists the $2^k$-th root of unity. It can be shown that $g^c$ is such a $2^k$-th root of unity, where $g$ is a primitive root of $p$.

const int mod = 7340033;
const int root = 5;
const int root_1 = 4404020;
const int root_pw = 1 << 20;

void fft(vector<int> & a, bool invert) {
int n = a.size();

for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;

if (i < j)
swap(a[i], a[j]);
}

for (int len = 2; len <= n; len <<= 1) {
int wlen = invert ? root_1 : root;
for (int i = len; i < root_pw; i <<= 1)
wlen = (int)(1LL * wlen * wlen % mod);

for (int i = 0; i < n; i += len) {
int w = 1;
for (int j = 0; j < len / 2; j++) {
int u = a[i+j], v = (int)(1LL * a[i+j+len/2] * w % mod);
a[i+j] = u + v < mod ? u + v : u + v - mod;
a[i+j+len/2] = u - v >= 0 ? u - v : u - v + mod;
w = (int)(1LL * w * wlen % mod);
}
}
}

if (invert) {
int n_1 = inverse(n, mod);
for (int & x : a)
x = (int)(1LL * x * n_1 % mod);
}
}

Here the function inverse computes the modular inverse (see Modular Multiplicative Inverse). The constants mod, root, root_pw determine the module and the root, and root_1 is the inverse of root modulo mod.

In practice this implementation is slower than the implementation using complex numbers (due to the huge number of modulo operations), but it has some advantages such as less memory usage and no rounding errors.

Multiplication with arbitrary modulus

Here we want to achieve the same goal as in previous section. Multiplying two polynomial $A(x)$ and $B(x)$, and computing the coefficients modulo some number $M$. The number theoretic transform only works for certain prime numbers. What about the case when the modulus is not of the desired form?

One option would be to perform multiple number theoretic transforms with different prime numbers of the form $c 2^k + 1$, then apply the Chinese Remainder Theorem to compute the final coefficients.

Another options is to distribute the polynomials $A(x)$ and $B(x)$ into two smaller polynomials each \begin{align} A(x) &= A_1(x) + A_2(x) \cdot C \\ B(x) &= B_1(x) + B_2(x) \cdot C \end{align} with $C \approx \sqrt{M}$.

Then the product of $A(x)$ and $B(x)$ can then be represented as: $$A(x) \cdot B(x) = A_1(x) \cdot B_1(x) + \left(A_1(x) \cdot B_2(x) + A_2(x) \cdot B_1(x)\right)\cdot C + \left(A_2(x) \cdot B_2(x)\right)\cdot C^2$$

The polynomials $A_1(x)$, $A_2(x)$, $B_1(x)$ and $B_2(x)$ contain only coefficients smaller than $\sqrt{M}$, therefore the coefficients of all the appearing products are smaller than $M \cdot n$, which is usually small enough to handle with typical floating point types.

This approach therefore requires computing the products of polynomials with smaller coefficients (by using the normal FFT and inverse FFT), and then the original product can be restored using modular addition and multiplication in $O(n)$ time.

Applications

DFT can be used in a huge variety of other problems, which at the first glance have nothing to do with multiplying polynomials.

All possible sums

We are given two arrays $a[]$ and $b[]$. We have to find all possible sums $a[i] + b[j]$, and for each sum count how often it appears.

For example for $a = [1,~ 2,~ 3]$ and $b = [2,~ 4]$ we get: then sum $3$ can be obtained in $1$ way, the sum $4$ also in $1$ way, $5$ in $2$, $6$ in $1$, $7$ in $1$.

We construct for the arrays $a$ and $b$ two polynomials $A$ and $B$. The numbers of the array will act as the exponents in the polynomial ($a[i] \Rightarrow x^{a[i]}$); and the coefficients of this term will by how often the number appears in the array.

Then, by multiplying these two polynomials in $O(n \log n)$ time, we get a polynomial $C$, where the exponents will tell us which sums can be obtained, and the coefficients tell us how often. To demonstrate this on the example: $$(1 x^1 + 1 x^2 + 1 x^3) (1 x^2 + 1 x^4) = 1 x^3 + 1 x^4 + 2 x^5 + 1 x^6 + 1 x^7$$

All possible scalar products

We are given two arrays $a[]$ and $b[]$ of length $n$. We have to compute the products of $a$ with every cyclic shift of $b$.

We generate two new arrays of size $2n$: We reverse $a$ and append $n$ zeros to it. And we just append $b$ to itself. When we multiply these two arrays as polynomials, and look at the coefficient $c[n-1],~ c[n],~ c[2n-2]$ of the product $c$, we get: $$c[k] = \sum_{i+j=k} a[i] b[j]$$ And since all the elements $a[i] = 0$ for $i \ge n$: $$c[k] = \sum_{i=0}^{n-1} a[i] b[k-i]$$ It is easy to see that this sum is just the scalar product of the vector $a$ with the $(k - (n - 1))$-th cyclic left shift of $b$. Thus these coefficients are the answer to the problem, and we were still able to obtain it in $O(n \log n)$ time. Note here that $c[2n-1]$ also gives us the $n$-th cyclic shift but that is the same as the $0$-th cyclic shift so we don't need to consider that separately into our answer.

Two stripes

We are given two Boolean stripes (cyclic arrays of values $0$ and $1$) $a$ and $b$. We want to find all ways to attach the first stripe to the second one, such that at no position we have a $1$ of the first stripe next to a $1$ of the second stripe.

The problem doesn't actually differ much from the previous problem. Attaching two stripes just means that we perform a cyclic shift on the second array, and we can attach the two stripes, if scalar product of the two arrays is $0$.

String matching

We are given two strings, a text $T$ and a pattern $P$, consisting of lowercase letters. We have to compute all the occurrences of the pattern in the text.

We create a polynomial for each string ($T[i]$ and $P[I]$ are numbers between $0$ and $25$ corresponding to the $26$ letters of the alphabet): $$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}, \quad n = |T|$$ with $$a_i = \cos(\alpha_i) + i \sin(\alpha_i), \quad \alpha_i = \frac{2 \pi T[i]}{26}.$$

And $$B(x) = b_0 x^0 + b_1 x^1 + \dots + b_{m-1} x^{m-1}, \quad m = |P|$$ with $$b_i = \cos(\beta_i) - i \sin(\beta_i), \quad \beta_i = \frac{2 \pi P[m-i-1]}{26}.$$

Notice that with the expression $P[m-i-1]$ explicitly reverses the pattern.

The $(m-1+i)$th coefficients of the product of the two polynomials $C(x) = A(x) \cdot B(x)$ will tell us, if the pattern appears in the text at position $i$.

$$c_{m-1+i} = \sum_{j = 0}^{m-1} a_{i+j} \cdot b_{m-1-j} = \sum_{j=0}^{m-1} \left(\cos(\alpha_{i+j}) + i \sin(\alpha_{i+j})\right) \cdot \left(\cos(\beta_j) - i \sin(\beta_j)\right)$$ with $\alpha_{i+j} = \frac{2 \pi T[i+j]}{26}$ and $\beta_j = \frac{2 \pi P[j]}{26}$

If there is a match, than $T[i+j] = P[j]$, and therefore $\alpha_{i+j} = \beta_j$. This gives (using the Pythagorean trigonometric identity): \begin{align} c_{m-1+i} &= \sum_{j = 0}^{m-1} \left(\cos(\alpha_{i+j}) + i \sin(\alpha_{i+j})\right) \cdot \left(\cos(\alpha_{i+j}) - i \sin(\alpha_{i+j})\right) \\ &= \sum_{j = 0}^{m-1} \cos(\alpha_{i+j})^2 + \sin(\alpha_{i+j})^2 = \sum_{j = 0}^{m-1} 1 = m \end{align}

If there isn't a match, then at least a character is different, which leads that one of the products $a_{i+1} \cdot b_{m-1-j}$ is not equal to $1$, which leads to the coefficient $c_{m-1+i} \ne m$.

String matching with wildcards

This is an extension of the previous problem. This time we allow that the pattern contains the wildcard character $*$, which can match every possible letter. E.g. the pattern $a*c$ appears in the text $abccaacc$ at exactly three positions, at index $0$, index $4$ and index $5$.

We create the exact same polynomials, except that we set $b_i = 0$ if $P[m-i-1] = *$. If $x$ is the number of wildcards in $P$, then we will have a match of $P$ in $T$ at index $i$ if $c_{m-1+i} = m - x$.


text:
# I2C Communication Between STM32F3 and SSD1306

I am trying to write data to my 128x32 OLED display. I researched it online and found that it has the SSD1306 controller connected to the display. It uses the I2C protocol and it only has 4 pins (VCC, GND, SDA, SCL). I am using the SMT32F303RET as my main controller and i want to write some data on the display over the I2C connection. I am programming the controller using registers and I am not using any other external libraries other then the "stm32f3xx.h". I wish to stay this way because I am learning a lot more then when I'am using finished libraries.

I am connecting the SDA and SCL pins of the display directly to the SDA and SCL pins of my controller. I am setting the SDA and SCL pins as pull-up trough software.

simulate this circuit – Schematic created using CircuitLab

My main problem is that i can't get the I2C communication working properly. I have reed through all the I2C documentation in the reference maunual for the STM32F303RET and folow the steps carefully. Also I followed the rules and information given in the data sheet for the SSD1306 controller. But I had no luck...

This is the code I wrote for configuring the I2C and writing data trough it:

void i2c_init() {
//Enable I2C clock
RCC->APB1ENR |= RCC_APB1ENR_I2C2EN;

//Pin configuration
RCC->AHBENR |= RCC_AHBENR_GPIOFEN;

GPIOF->MODER |= GPIO_MODER_MODER0_1 | GPIO_MODER_MODER1_1;
GPIOF->MODER &= ~(GPIO_MODER_MODER0_0 | GPIO_MODER_MODER1_0);

GPIOF->OTYPER |= GPIO_OTYPER_OT_0 | GPIO_OTYPER_OT_1;

GPIOF->OSPEEDR &= ~(GPIO_OSPEEDER_OSPEEDR0 | GPIO_OSPEEDER_OSPEEDR1);

GPIOF->PUPDR |= GPIO_PUPDR_PUPDR0_0 | GPIO_PUPDR_PUPDR1_0;
GPIOF->PUPDR &= ~(GPIO_PUPDR_PUPDR0_1 | GPIO_PUPDR_PUPDR1_1);

GPIOF->AFR[0] |= 0x44;

//Timing configuration
I2C2->TIMINGR = 0x0000020C;

//CR2 configuration
I2C2->CR2 |= I2C_CR2_NACK | (0x3d << 1);

//CR1 configuration
I2C2->CR1 |= I2C_CR1_ANFOFF;

//Peripheral enable
I2C2->CR1 |= I2C_CR1_PE;
}

void i2c_write() {
I2C2->CR2 &= ~(I2C_CR2_RD_WRN);
I2C2->CR2 |= I2C_CR2_START | (1 << 16);

while(I2C2->CR2 & I2C_CR2_START);

I2C2->TXDR = (uint8_t)0xA5;

while(!(I2C2->ISR & I2C_ISR_TXE));

I2C2->CR2 = I2C_CR2_STOP;

while (I2C2->CR2 & I2C_CR2_STOP);
}

The main error I am getting is NACK (not acknowledged). I know this because the NACKF and STOPF bits in the ISR register turn on as soon as I enable the START bit in the CR2 register. Also before I change some timing settings I was getting the ARLO (arbitration lost) error.

• understand that some of these inexpensive displays do not ack, write your own code or change the library not to look for an ack. rarely do devices conform to i2c nor spi specs, always assume they dont, and if they do then great. – old_timer May 26 '19 at 18:46
• An I2C peripheral that "does not ACK" is simply not an I2C peripheral of any sort, as the ACK is fundamental to the very idea of the protocol. An SSD1306 most defintiely does ACK when correctly addressed. – Chris Stratton Jul 11 at 3:37

Not meaning to solve your specific problem with i2c, here is some advice :

SSD1306 also supports SPI and 8-bit parallel. You may want to switch to SPI. You will get faster communication while still using reasonnably few pins (3 pins). Communicating faster with your OLED display will provide a better refresh rate and avoid the sweeping effect when pushing pixels to the display controller.

I think it's worth considering it.

• Well if the OLED he has is configured in I²C mode, he can't change it - the decision is usually done on the glass under the blob of glue which protects the controller. I do agree that SPI is a better choice, but sometimes it's not an option. – Arsenal May 26 '19 at 9:48
• @Arsenal , ah, true, i missed that :( – FrProg34 May 26 '19 at 9:57

In general, internal pull-up\down resistor in ICs are usually what is called 'weak' pull up\down. This means that the resistor value doing the pulling is large (I would say typically >50kohm, and you can find the exact value in the data-sheet).
This can contribute to 2 factors:
1. current through the pull up which impacts the time it takes the board and chip capacitance to charge (signal rise time)
2. current carrying capacity of the relative pin. Smaller resistance values allows greater currents which might damage the IC

Additionally, you have to consider logic levels required between your STM32 and the display controller. If they are working in different logic levels (eg. 3.3V and 5V) it is possible that your signals don't cross the required thresholds.

Lastly, if you post your schematics it will be much easier to comment, rather then just general comments.

• Thank you for the quick response! I tried what you sugested. I found the value of the built in pull-up resistor and the value is around 40kohm. I then tried to connect my own pull-up resistor, setting the GPIO to no pull-up pull-down. I tried connecting it to 5V and 3.3V and changing the suply voltage to the ssd1306 controller. Also tried a lot of different resistor values ranging from 1kohm up to 50kohm. Al of these tests gave me the same result. There was no error this time, but the I2C was busy after setting the START bit. I guess the controller didn't receive anything. – jose2000 May 26 '19 at 12:06
• In that case I would suggest to get your hands on a nice and simple scope and start probing the lines to see whether there are signals actually coming out. – ZelmaB May 27 '19 at 14:15


text:
# tag: cryptography vs security

The question Break an authentication protocol based on a pre-shared symmetric key was tagged with both and .

What is the difference between these tags, and when should each be used?

• I retagged the question as "crypto" only, according to my answer below. Mar 17 '12 at 23:38
• security is far more general than cryptography. Mar 18 '12 at 13:06

My stand on it is similar to the distinction between crypto.SE and ITsecurity.SE (which is slightly vague and sometime ambiguous)

is for more theoretical primitives , algorithms and methods and the their analysis. (e.g, AES, ZK-proofs, signature schemes, etc.)

is for security in real-world systems and practical questions.(e.g., computer forensics, DDS and network security, etc.)

• I think the main point is that security is way broader than crypto.
– Raphael Mod
Mar 18 '12 at 0:57

I wasn't sure what to use. I'm not too keen on here either, but I do want have a way to distinguish mathematical primitives from abstract cryptography. How about , for that matter?

• can you explain what abstract-crypto will include? Mar 17 '12 at 23:49
• @RanG. I've heard it used for the study of protocols in which crypto primitives are treated as black boxes (“$E$ is symmetric encryption algorithm, $H$ is a hash, …”). I don't know how widespread this terminology is. Mar 18 '12 at 0:17
• this is just plain theoretical cryptography: assuming one-way functions, (good) encryptoin schemes, etc. I don't see the need to call it theoretical-cryptography Mar 18 '12 at 0:22
• see this. But I don't think there is need to have separate crypto tags for these. (ps: abstract crpto is a very bad name.) Mar 18 '12 at 3:02
• If anything protocols should be cryptographic-protocols. Abstract-cryptography seems to be going too fine-grained. Mar 18 '12 at 13:10


text:
day_2_10-15-2015

# The Analog Dog Blog

## Day 2 -- Transistor Characterization

### Model Parameter Extraction and ID-VGS Characterization

Recall the long channel transistor model, also know as the square law model.

If $V_{DS} < (V_{GS}-V_{TH})$ and $V_{GS}>V_T$ this is called the linear or triode region.

In this mode of operation, the drain current increases linearly with $V_{GS}$.

$I_D=KP_n\frac{W}{L}\left [\left ( V_{GS}-V_T \right ) V_{DS}-\frac{1}{2}V_{DS}^{2} \right ]$

If $V_{DS} > (V_{GS}-V_{TH})$ and $V_{GS}>V_T$, the device is said to be operating in saturation or square law mode.

The drain current increases as the square of the gate to source voltage.

$I_D=\frac{1}{2}KP_n\frac{W}{L}\left ( V_{GS}-V_T \right )^2(1 + \lambda(V_{DS}-V_{DS,SAT}))$

$V_{DS,SAT}= V_{GS} - V_T$.

Before one can use the model shown above, we need to extract the model parameters $KP_n$, $V_T$, and $\lambda$.

Let's start by extracting $KP_n$ and Vt for a long channel device. If we make L large, $\lambda$ the channel length modulation parameter goes to 0.

$I_D=\frac{1}{2}KP_n\frac{W}{L}\left ( V_{GS}-V_T \right )^2$

Taking the square root of both sides yields:

$\sqrt{I_D}=\sqrt{\frac{1}{2}KP_n\frac{W}{L}}*(V_{GS}-V_T)$

The above equation is just a straight line, so the math is easier to work with. To get $KP_n$ and $V_T$, just solve the two equations two unknowns from the model data. This is not the most physcally correect thing to do. The model does not follow the square law exactly due to secondary effects like mobility degredation and series resistance. Atleast for DC operating point problems this will make the hand calculations the most accurate.

I used values of $V_{GS}$=1.5 and $V_{GS}=4.0$ to generate the model seen below. $KP_n$=7.64e-5 and $V_T$=0.602

The red line is the SPICE model and the blue line is the square-law model that was just extracted.


text:
Next: Bibliography Up: Solving One-Sided Equations in Previous: 4. Conclusions

# 5. Prefix Gröbner Bases in and

In [3] it was shown how to characterize and compute prefix Gröbner bases in monoid rings where is presented by a finite convergent string rewriting system. Here we want to show that if a finite prefix Gröbner basis exists for a right ideal, then there is also a finite reduced prefix Gröbner basis and we want to list two important properties of such a basis needed to characterize the solutions of the homogeneous equations in the previous section. Further we outline how the technique of Gröbner bases extends to right -modules .

In order to use elements of as rules for reduction we need an ordering on and one on : We will first specify a total well-founded ordering on 6:

and iff or 7.

As ordering on we take the one induced by the completion ordering on of the string rewriting system. This ordering has the advantage that it is admissible with respect to concatenation and we have where and the multiplication on is realized by normal form computation with respect to the string rewriting system presenting .

Then for any we can characterize its largest term as head term , the coefficient of this term as , and .

Let us briefly recall the reduction relation used for in [3].

Definition 4   Let , be two non-zero polynomials in .
We say prefix reduces to at in one step, i.e. , if
(a)
for some , i.e.  is a prefix of as a word.
(b)
and with , , and .
(c)
.

Prefix Gröbner bases with respect to this reduction relation then can be characterized using the concept of prefix s-polynomials combined with some extra polynomials which are necessary to describe the whole right ideal congruence by prefix reduction.

Definition 5   Given two polynomials with for . If there is with we have to distinguish:
1. If , , where , , we get the following superposition causing a critical pair:

This gives us the prefix s-polynomial

2. If , , where , , we get the following superposition causing a critical pair:

This gives us the prefix s-polynomial

Prefix Gröbner bases then can be characterized by the following theorem from [6]:

Theorem 6   Equivalent are:
1. .
• For all we have .
• For all , we have .

The set then is called a prefix Gröbner basis of the right ideal it generates. Notice that without loss of generality we can always assume that all head coefficients of its polynomials are greater than zero.

Lemma 7   Let be a finite prefix Gröbner basis and such that . Then 8 is again a prefix Gröbner basis of the same right ideal.

Proof : 1.1
This follows as can be shown to be a ring with a reduction relation fulfilling the axioms (A1) - (A4) for reduction rings as presented in [4]. It is easy to see that the reduction relation is terminating (A1), preserves the right ideal congruence (A2) and for any non-zero polynomial holds (A3). The important axiom allowing to reduce prefix Gröbner bases without losing the prefix Gröbner basis property9(A4) holds if for any , and imply .
Let at some monomial , i.e.  for some , , , and . Moreover, let at some monomial , i.e.  for some , , , and . We have to distinguish the following cases:
1. If then we are done at once, since and hence .
2. If we have to be more careful as , i.e. the reduction step took place at the head monomial of and , .
1. If then . We get . Now either or there exist such that with . In either case then can be prefix reduced using .
2. If then and hence and imply that is prefix reducible by .
Now it is easy to see that is again a prefix Gröbner basis of the same right ideal. If some polynomial is reducible by it will also be reducible by . q.e.d.

1 Now a prefix Gröbner basis is called reduced if no is prefix reducible by .

Lemma 8   Let be a reduced prefix Gröbner basis. Further let such that and for some . Then for some and .

Proof : 1.1
We show that the other cases are not possible.
1. Assume that .
Then without loss of generality we can also assume and hence , , and . Therefore, contradicting the assumption that is supposed to be reduced.
2. Now let . We have to distinguish two cases:
1. If again we have , , and . This situation now gives rise to an s-polynomial . Notice that this s-polynomial has head monomial and hence is neither reducible by nor by . On the other hand, as is a prefix Gröbner basis, the s-polynomial must be reducible to zero using elements of . Additionally we know that is reducible by this s-polynomial which implies that then must also be reducible by some element in contradicting our assumption of being reduced.
2. If we get , , and . Then as before contradicting the assumption that is supposed to be reduced.
Hence the only possible case remains to be for some and . As before this gives rise to an s-polynomial, but now we cannot conclude that one of the polynomials , is reducible by it hence since we get no contradiction to being reduced, this case is possible. q.e.d.

1

If we want to compute prefix Gröbner bases of submodules in a right -module this can be done by introducing a reduction relation and completing it. Provided a finite basis , ..., of its elements can be represented by polynomials . A reduction relation now can be defined as follows:

Definition 9   Let , . We say that prefix reduces to at in one step, denoted by , if
(a)
for ,
(b)
with , and
(c)
.

Hence prefix reduction in reduces to prefix reduction in . One can show that together with this reduction relation fulfills (A1) - (A4) for reduction rings as specified in [4] and Gröbner bases can be characterized using g- and m-polynomials. The basic idea is to compute a prefix Gröbner basis of a right -module generated by a set of vectors by modifying the set according to the following steps:
1. initialize a counter ,
2. compute a prefix Gröbner basis of the right ideal generated by the head terms of those vectors with which is in fact a prefix Gröbner basis computation in which also affects the components of the vectors involved below'' the i-th component,
3. compute a set of solutions for the homogeneous equation related to those vectors with hence generating new generators for the submodule with non-zero component larger than ,
4. continue for until all components have been handled.

Next: Bibliography Up: Solving One-Sided Equations in Previous: 4. Conclusions
| ZCA Home | Reports |


text:
# Difference between revisions of Optics related math

Here's a page with maths related to diopters and glasses.

You don't really need to know any of this stuff to improve your eyesight, but it's good to know for deeper understanding

## Lenses

The image shows a typical converging lens. The three rays drawn each have an interesting characteristic:

• the top ray enters the lens parallel with the optic axis, and so passes through the focal point on the other side
• the middle ray passes through the optical centre of the lens, and is undeviated
• the bottom ray passes through the focal point on the incident side, and so emerges parallel to the optic axis

### The thin lens equation

${\displaystyle {\frac {1}{f}}=({\frac {1}{s}})+({\frac {1}{s'}})}$ where

• ${\displaystyle f}$ = focal length of lens
• ${\displaystyle s}$ = distance to object (${\displaystyle S_{1}}$ on the picture)
• ${\displaystyle s'}$ = distance to image (${\displaystyle S_{2}}$ on the picture)

### Infinity

The term object at infinity is often used. When ${\displaystyle s=\infty }$ is substituted into the thin lens equation, that term vanishes, so that the focal length is then just the image location. For any sufficiently large object distance, the contribution from the reciprocal becomes negligible.

As the object approaches the lens, the outgoing rays converge less and less, until the object reaches the focus of the lens (${\displaystyle s=f}$), and the transmitted light is parallel - we say it "focuses at ${\displaystyle s'=\infty }$", which means it never comes together into a focus. (This can also be described as a virtual image at ${\displaystyle s'=-\infty }$ - see below.)

### Virtual image

When the object is brought even closer to the lens (${\displaystyle s) the emerging rays are now diverging. When substituted into the equation, ${\displaystyle s'<0}$. This is interpreted as a virtual image, behind the lens. This is the mode in which reading glasses (plus lenses) are used - the eye is able to focus on the virtual image which appears to be further away than the real source object.

### Diverging lens

A diverging lens behaves in a similar way, but for distant objects - the light rays incident from the source object are refracted outwards so that they are diverging even faster. Again, a virtual focus is said to form behind the lens. The thin lens equation still works as long as you use negative numbers to describe both the (virtual) image location and the focal length.

The corrective lens for myopia is a diverging lens. It works by forming a virtual image of distant objects, and it is this virtual image that the near-sighted eye is able to focus on.

### Diopters are inverse meters

Intuitively, the more powerful a lens is, the more rapidly it can bring incoming light to a focus. So the power is defined as the inverse of the focal length.

Remember that 100cm = 1m.

${\displaystyle D={\frac {1}{meters}}}$

conversely

${\displaystyle meters={\frac {1}{D}}}$

## Calculating correction

How to calculate the strength of corrective lenses

### From 20/20 prescription

The advantage of calculating the strength of differentials as a reduction from full prescription is that you don't have to worry about the cylinder element - just preserve that part.

Assuming you are wearing your full 20/20 correction (or even if you are fortunate to be emmetropic), the eye wants to receive parallel incident light to be relaxed. So we can use a simple geometric argument to calculate the strength of the (converging) lens which should be interposed : an object placed at the focus of a converging lens will result in parallel outgoing light ("focus at infinity"). This parallel light is exactly what the (fully corrected) eye wants to receive.

But rather than actually placing such a lens in front of your full prescription, simply add that value (being careful with signs).

ie if your screen is 50cm away, that corresponds to a power of ${\displaystyle {\frac {1}{0.5}}=2D}$. So that's the value you'd add to your full prescription (resulting in a less-negative lens).

### From blur horizon of naked eye

Note that this does not take either cylinder (astigmatism) or vertex distance into account.

Your cm measurement gives you the distance the eye can see when it is fully relaxed. You want a (diverging) corrective lens which puts a virtual image of the source object there. So we can solve the thin lens equation to find ${\displaystyle f}$ for an arbitrary source object distance ${\displaystyle s}$ given ${\displaystyle s'=-cm}$.

For full correction, that's easy : ${\displaystyle s=\infty }$ and so ${\displaystyle f=s'}$. E.g. if your blur horizon is 20cm you need a -5D correction.

For differentials to use a screen at, say, 50cm, just use ${\displaystyle {\frac {1}{f}}={\frac {1}{0.50}}+-{\frac {1}{0.20}}=-3D}$. (Which is consistent with the previous version, adding 2D to the calculated full correction of -5D.)

## Visual acuity equation

${\displaystyle ({\frac {font\ height}{distance\ to\ sign}})({\frac {180}{pi}})\times 60=arcminutes=a}$

Note: 5Arcminutes = 20/20

Set up proportion: ${\displaystyle {\frac {a}{({\frac {20}{x}})}}={\frac {5}{({\frac {20}{20}})}}}$

### Visual acuity (mm/metres)

${\displaystyle {\frac {font\ height(mm)}{distance\ to\ sign(m)}}\times 13.75=denominator\times of{\frac {20}{x}}}$

### Visual acuity (in/feet)

${\displaystyle {\frac {font\ height(in)}{distance\ to\ sign(ft.)}}\times 1146=denominator\times of{\frac {20}{x}}}$

With text that we are familiar with, the brain may clear up that text more than our vision would actually allow.[1]

## Average axial length accomodation/rate of change

• The typical emmetropic eye is 25mm
• change in axial length of 1mm = 3D

If someone with typical eyes wanted to adapt say 20/20 to .25 less normalized within 3-4 months would need to decrease axial length 0.083mm about 0.92microns/day - 0.69microns/day average Credit: Mark Podowski