text:
Examples of hyperbolic groups

What are some other classes of word-hyperbolic groups other than the finite groups, fundamental groups of surfaces with Euler characteristics negative and virtually free groups?

• All introductions to hyperbolic groups I can think of abound of examples.
– YCor
Aug 6, 2019 at 11:04
• Can you tell me some of those texts because so far all the books that I have referred to (papers by Bowditch, the book metric spaces of non-positive curvature, book by Clara Loh, GGT ) cite only these classes of examples. Aug 6, 2019 at 11:10
• The Bridson-Haefliger book certainly mentions more.... it should mention relation to negative curvature somewhere... mention stability under free product. Of course I also think of the Ghys-Harpe book, which is in French.
– YCor
Aug 6, 2019 at 11:12

Below are some sources of hyperbolic groups. Of course, the list is far from being exhaustive.

1. Groups defined by generators and relations:

• Finitely generated free groups, as their Cayley graphs are simplicial trees.
• If $$\varphi$$ is an atoroidal automorphism of a free group $$\mathbb{F}_n$$, then the extension $$\mathbb{F}_n \rtimes_\varphi \mathbb{Z}$$ is hyperbolic.
• One-relator groups with torsion, namely groups admitting a presentation of the form $$\langle x_1, \ldots, x_n \mid r^m=1 \rangle$$ with $$m \geq 2$$, are hyperbolic.

• Coxeter groups not containing $$\mathbb{Z}^2$$ are hyperbolic. (See Theorem 12.6.1 in Davis' book The geometry and topology of Coxeter groups for a better characterisation.) As a nice particular case, right-angled Coxeter groups defined by finite square-free graphs are hyperbolic.

• Generalising hyperbolic right-angled Coxeter groups, graph products of finite groups over square-free graphs are hyperbolic.
• If $$\Gamma$$ is a topological graph which does not contain two disjoint loops, then the braid group $$B_2(\Gamma)$$ is hyperbolic.
• Small cancellation groups C'(1/6) or C'(1/4)-T(4). A very rich source of two-dimensional hyperbolic groups.
• Random groups in Gromov's density model are hyperbolic and non-elementary below a given density.
2. Fundamental groups:

• Fundamental groups of compact negatively curved Riemannian manifolds are hyperbolic.
• Fundamental groups of hyperbolic 3-manifolds. A general construction is to take a hyperbolic 3-manifold of finite volume and to "fill in" its cusps with tori in different ways. The keyword is Dehn fillings.
• Uniform lattices in real, complex and quaternionic hyperbolic spaces are hyperbolic. Arithmetic constructions may lead to explicit examples.
• If $$f$$ is a pseudo-Anosov homeomorphism of a closed surface $$S$$, then $$\pi_1(S) \rtimes_\varphi \mathbb{Z}$$ is hyperbolic, where $$\varphi$$ denotes the automorphism of $$\pi_1(S)$$ induced by $$f$$. (A reference is Otal's monograph Le théorème d'hyperbolisation pour les variétés fibrées de dimension 3; also, a generalisation to free groups of pseudo-Anosov homeomorphisms can be found in Farb and Mosher's article Convex cocompact subgroups of mapping class groups.)
3. Constructions

• Dehn fillings are now defined purely algebraically, and it is possible to create hyperbolic groups by quotienting relatively hyperbolic groups for instance, or even to create exotic hyperbolic groups from classical hyperbolic groups.
• The family of hyperbolic groups is also stable under various operations, including commensurability, some graphs of groups, and some graph products. For instance, free products (as mentioned by Yves in the comments).

I can add a few precise references if some examples interest you. Otherwise, you have some keywords to help you in your research.

• Thank you, much appreciated! I will try finding the sources on the basis of the keywords provided. Aug 6, 2019 at 14:23
• It's not stable under graph product (not even under direct products).
– YCor
Aug 6, 2019 at 22:56
• "Coxeter groups defined by square-free graphs": probably you don't consider the standard graphs (where edges labeled by $2$ are omitted) but omit instead only edges labeled $\infty$?
– YCor
Aug 6, 2019 at 22:58
• Random groups in Gromov's density model are hyperbolic in all densities; below some density rather ensures they're non-elementary.
– YCor
Aug 6, 2019 at 23:00
• In the last point, I didn't mean that the family of hyperbolic groups is stable by all graph products, but only some of them (similarly for graphs of groups). I refer to Meier's article When is a graph product of hyperbolic groups hyperbolic? for a precise characterisation. Aug 7, 2019 at 5:50


text:
# To purchase new furniture, the owner of a restaurant borrowed $5,000.00 for 2 ye and paid$350.00 simple interest on the loan. What rate of interest did she pay?

Dec 19, 2016

See the explanation: There is ambiguity in the question.

#### Explanation:

$\textcolor{red}{\text{Possible ambiguity in the question}}$

Was the interest the total paid of the 2 years or was it the amount paid each year for a period of 2 years. If the latter then she paid $700.00 as a total. $\textcolor{b l u e}{\text{Condition 2 is the most likely intended meaning}}$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ $\textcolor{b l u e}{\text{Initial condition }}$Expressing the total interest over the full time span as a fraction of the principle sum gives us: $\frac{350}{5000}$$\textcolor{b l u e}{\text{Determine the percentage interest in total over the full time span}}$To change this to a percentage of the principle sum we need to modify it such that the 5000 becomes 100. To change the 5000 into 100 divide it by 50. However, to maintain proportionality for multiply or divide what we do to the bottom we do to the top so we have: $\frac{350}{5000} \equiv \frac{350 \div 50}{5000 \div 50} = \frac{7}{100}$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ $\textcolor{b l u e}{\text{Condition 1:- For the condition: $350 total paid over the 2 years}}$

color(brown)("Percentage paid annually was "1/2xx7/100 = 3.5/100 = 3.5%
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
$\textcolor{b l u e}{\text{Condition 2:-For the condition:$350 total paid over 1 year}}\$

color(brown)("Percentage paid annually was "7/100 = 7%

format: plain


text:
# Compared growth of the number of syntactic classes and Nerode classes.

For a language L ⊆ Σ^*, define the syntactic congruence of L as the least congruence on Σ^* that saturates L, i.e. :

u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].

Now define the Nerode equivalence as the following right congruence :

u ∼ v ⇔ (∀ x)[ux ∈ L ↔ vx ∈ L].

Let [u] be the equivalence class of u with respect to and 〈u〉 with respect to . Now define i(n) to be the number of different [u] for u of size n, and define j(n) in a similar fashion for .

Now the question is, how do the two functions relate ?

For instance, a standard theorem (Kleene-Schützenberger, I believe) says that i(n) is bounded by a constant whenever j(n) is, and reciprocally.

Question: Is there any other result in this trend? What if one of them is polynomial, for instance?

• Certainly i(n) is always an upper bound on j(n), so presumably you are only asking about implication in the other direction, for example: if j(n) is bounded above by a polynomial, must i(n) be as well? – Joshua Grochow Aug 18 '10 at 2:07
• Well, the other way around still makes sense, no? For instance I may ask: if i(n) is exponential, is there a simple criterion from which I can conclude that j(n) is also exponential? – Michaël Cadilhac Aug 18 '10 at 13:14
• Indeed. I was just thinking in terms of upper bounds, but of course you are correct. – Joshua Grochow Aug 18 '10 at 15:12

It seems that this paper http://arxiv.org/abs/1010.3263 may be relevant to your question.

The abstract states:

The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n-1}$ is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity $n^{n-1}+n-1$, and two-sided ideals and factor-closed languages of syntactic complexity $n^{n-2}+(n-2)2^{n-2}+1$.

Thus, as far as I understand, this answers your question about the sizes of syntactic and Myhill-Nerode semigroup: in general, syntactic congruence may have exponentially many classes than Myhill-Nerode relation.

The last comment. Usually the finitness of both semigroups for regular languages is attributed to M.Rabin and D.Scott (Finite automata and their decision problems. IBM Jourmal. April 1959). In particular, it follows from the text of Rabin and Scott that the number of syntactic classes does not exceed $n^n$, where $n$ is the number of Myhill-Nerode classes.

• Could you please expand your answer to explain the relevance? – Dave Clarke Feb 9 '11 at 10:18
• Just look through the paper! – Sergey Feb 9 '11 at 10:27
• I'm sorry, I inserted invalid link. Actually I was intended to give not the answer (in some sense the answer is contained in the paper I'd mentioned) but a comment, but unfortunately I don't know how to do it technically – Sergey Feb 9 '11 at 10:31
• By the way, as it follows from the paper listed above there could be exponentially more syntactic classes than Myhill-Nerode classes. – Sergey Feb 9 '11 at 11:05
• It would be nice if you summarized the result of the paper which is relevant to this question, and it will turn into a perfect answer here. Please :) Some of us (me) are pretty interested to see answers to a long-standing unanswered question here! – Hsien-Chih Chang 張顯之 Feb 9 '11 at 14:01


text:
# Problem 1

Tangents AP and AQ are drawn to circle with centre O, from an external point A. Prove that ∠PAQ=2.∠ OPQ

## Interpretation of the problem

1. O is the centre of the circle and tangents AP and AQ are drawn from an external point A.
2. OP and OQ are the radii.
3. The students have to prove thne angle PAQ=twise the angle OPQ.

## Concepts used

1. The radii of a circle are equal.
2. In any circle the radius drawn at the point of contact is perpendicular to the tangent.
3. The tangent drawn from an external point to a circle a] are equal b] subtend equal angle at the centre c] are equally inclined to the line joining the centre and extrnal point.
4. Properties of isoscles triangle.
5. Properties of quadrillateral ( sum of all angles) is 360 degrees
6. Sum of three angles of triangle is 180 degrees.

## Algorithm

OP=OQ ---- radii of the same circle OA is joined.
∠APO=∠AQO=${\displaystyle 90^{0}}$ [radius drawn at the point of contact is perpendicular to the tangent]
∠PAQ+∠POQ=${\displaystyle 180^{0}}$
Or, ∠PAQ+∠POQ=${\displaystyle 180^{0}}$
∠PAQ = ${\displaystyle 180^{0}}$-∠POQ ----------1
Triangle POQ is isoscles. Therefore ∠OPQ=∠OQP
∠POQ+∠OPQ+∠OQP=${\displaystyle 180^{0}}$
Or ∠POQ+2∠OPQ=${\displaystyle 180^{0}}$
2∠OPQ=${\displaystyle 180^{0}}$- ∠POQ ------2
From 1 and 2
∠PAQ=2∠OPQ

# Problem-2

In the figure two circles touch each other externally at P. AB is a direct common tangent to these circles. Prove that
a). Tangent at P bisects AB at Q
b). ∠APB=90° (Exescise-15.2, B.3)

## Interpretation of the problem

1. In the given figure two circles touch externally.
2. AB is the direct common tangent to these circles.
3. PQ is the transverse common tangent drawn to these circles at point P.
4. Using the tangent properties students have to show AQ=BQ and ∠APB=90°

## Concepts used

1. The tangent drawn from an external point to a circle
a) are equal
b] subtend equal angle at the center
c] are equally inclined to the line joining the center and external point.
2. Angle subtended by equal sides are equal.
3. Axiom-1:- "Things which are equal to same thing are equal"

## Algorithm

In the above figure AB is direct common tangent to two circles and PQ is the Transverse common tangent.
a)
AQ=QP and BQ=QP (Tangents drawn from external point are equal)
By axiom-1, AQ=BQ
∴tangent at P bisects AB at Q.
b)
Let ∠QBP=x˚

∴∠QPB=x˚ (∵PQ=BQ)
Now Let ∠PAQ=y˚
∠QPA=y˚ (∵ PQ=AQ)
∴In △PAB

∠PAB+∠PBA+∠APB=180˚

y˚+x˚+(x˚+y˚)=180˚
2x˚+2y˚=180˚
2(x˚+y˚)=180˚
x˚+y˚=90˚
∴ ∠APB=90˚

# problem 3 [Ex-15.2 B.7]

Circles ${\displaystyle C_{1}}$ and ${\displaystyle C_{2}}$ touch internally at a point A and AB is a chord of the circle${\displaystyle C_{1}}$ intersecting ${\displaystyle C_{2}}$ at P, Prove that AP= PB.

## Concepts used

1. The radii of a circle are equal
2. Properties of isosceles triangle.
3. SAS postulate
4. Properties of congruent triangles.

## Prerequisite knowledge

1. The radii of a circle are equal.
2. In an isosceles triangle angles opposite to equal sides are equal.
3. All the elements of congruent triangles are equal.

## Algoritham

In ∆AOB
AO=BO [Radii of a same circle]
∴ ∠OAB = ∠OBA --------------I [∆AOB is an isosceles ∆}
Then,
In ∆AOP and ∆BOP,
AO = BO [Radii of a same circle]
OP=OP [common side]
∠OAP = ∠OBP [ from I]
∴ ∆AOP ≅ ∆BOP [SAS postulate]
∴ AP = BP [corresponding sides of congruent triangles ]

# problem-4

In the given Quadrilateral ABCD , BC=38cm , QB=27cm , DC=25cm and AD⊥DC find the radius of the circle.(Ex:15.2. A-6)

## Interpretation of problem

1. In the quadrilateral ABCD sides BC , DC & QB are given .

## Concepts used

1. Tangents drawn from an external point to a circle are equal.
2. In a quadrilateral, if all angles are equal and a pair of adjacent sides are equal then it is a square
3. In a circle, the radius drawn at the point of contact is perpendicular to the tangent

## Algorithm

In the fig BC=38 cm and BQ=27 cm
BQ=BR=27 cm (∵ by concept 1)
∴CR=BC-BR=38-27=11 cm
CR=SC=11 cm (∵ by concept 1)
DC=25 cm
∴ DS=DC-SC=25-11=14 cm
DS=DP=14 cm (∵ by concept 1)
∠D=∠S=∠P=90˚
⇒ ∠O=90˚
∴ DSOP is a Square
SO=OP=14 cm
hence Radius of given circle is 14 cm

# Problem 5 [Ex-15.2-B8]

A circle is touching the side BC of △ABC at P. AB and AC when produced are touching the circle at Q and R respectively. Prove that AQ =${\displaystyle {\frac {1}{2}}}$ [perimeter of △ABC].

## Algorithm

In the figure AQ , AR and BC are tangents to the circle with center O.
BP=BQ and PC=CR (Tangents drawn from external point are equal) ---------- (1)

Perimeter of △ABC=AB+BC+CA
=AB+(BP+PC)+CA
=AB+BQ+CR+CA ------ (From eq-1)
=(AB+BQ)+(CR+CA)
=AQ+AR ----- (From fig)
=AQ+AQ -- --- (∵AQ=AR)
=2AQ

∴ AQ = ${\displaystyle {\frac {1}{2}}}$ [perimeter of △ABC]

# Problem-6 [Ex-15.4-B3]

In circle with center O , diameter AB and a chord AD are drawn. Another circle drawn with OA as diameter to cut AD at C. Prove that BD=2OC.

## Algorithm

In figure, AB is the diameter of circle ${\displaystyle C_{1}}$ and AO is the diameter of the circle ${\displaystyle C_{2}}$
∠ADB=90° and ∠ACO=90° [∵angles in the semi circles]
∠DAB=∠CAO [∵common angles]
${\displaystyle {\frac {AB}{OA}}}$=${\displaystyle {\frac {BD}{OC}}}$=${\displaystyle {\frac {AD}{AC}}}$ [∵corresonding sides of a similar triangles are proportional]
But AB=2OA----1 (∵diameter is twice the radius of a cicle)
${\displaystyle {\frac {AB}{OA}}}$=${\displaystyle {\frac {BD}{OC}}}$
from (1)
${\displaystyle {\frac {2OA}{OA}}}$=${\displaystyle {\frac {BD}{OC}}}$
∴BD=2OC

# Problem-7 [Ex-15.4-A3]

In the figure AB=10cm,AC=6cm and the radius of the smaller circle is xcm. find x.

## Interpretation of the problem

1. In the given figure two circles touch internally.
2. OB and OF are the radii of the semicircle with center "O".
3. PC and PF are the radii of the circle with center "P".

## Ex 4.4.2

1. Suppose two chords of a circle are equidistant from the centre of the circle, prove that the chords have equal length.

DATA :- Let AB & CD are the two chords which are equidistant from the centre 'O' of the circle. [ Here OP is the perpendicular distance from the centre O to the chord AB and OQ is the perpendicular distance from the centre O to the chord CD] OP = OQ.

TO PROVE :- AB = CD,

CONSTRUCTION :- Join OA & OD.

PROOF :-

    {[Consider  In ∆AOP & ∆DOQ                              OA = OD                              OP = OQ                 Angle APO = Angle DQO                        ∆AOP ≡ ∆DOQ                             AP = DQ    Let  AB = AP + BP                 = AP + AP                 = 2AP           AB = 2DQ ---------- 1.   and  CD = CQ + DQ                 = DQ + DQ           CD = 2DQ --------- 2.  From equtn 1 & equtn 2            AB = CD

Radii of the circle Equi distances from circle

SAS Axiom

Acording to properties of SAS axiom.

Perpendicular drawn from centre to chord which bisect the chord, i.e. AP = BP.

Perpendicular drawn from centre to chord which bisect the chord, i.e. CQ = DQ Acording to AXIOM-1]}

angle

 Steps Explanation Explanation for thestep Write the step Explanation for thestep

|}


text:
# Properties

 Label 7056.2.b.m Level 7056 Weight 2 Character orbit 7056.b Analytic conductor 56.342 Analytic rank 0 Dimension 2 CM no Inner twists 2

# Related objects

## Newspace parameters

 Level: $$N$$ $$=$$ $$7056 = 2^{4} \cdot 3^{2} \cdot 7^{2}$$ Weight: $$k$$ $$=$$ $$2$$ Character orbit: $$[\chi]$$ $$=$$ 7056.b (of order $$2$$, degree $$1$$, minimal)

## Newform invariants

 Self dual: no Analytic conductor: $$56.3424436662$$ Analytic rank: $$0$$ Dimension: $$2$$ Coefficient field: $$\Q(\sqrt{-3})$$ Defining polynomial: $$x^{2} - x + 1$$ Coefficient ring: $$\Z[a_1, \ldots, a_{5}]$$ Coefficient ring index: $$2$$ Twist minimal: no (minimal twist has level 112) Sato-Tate group: $\mathrm{SU}(2)[C_{2}]$

## $q$-expansion

Coefficients of the $$q$$-expansion are expressed in terms of a primitive root of unity $$\zeta_{6}$$. We also show the integral $$q$$-expansion of the trace form.

 $$f(q)$$ $$=$$ $$q + ( 1 - 2 \zeta_{6} ) q^{5} +O(q^{10})$$ $$q + ( 1 - 2 \zeta_{6} ) q^{5} + ( 1 - 2 \zeta_{6} ) q^{11} + ( 3 - 6 \zeta_{6} ) q^{17} + 7 q^{19} + ( 5 - 10 \zeta_{6} ) q^{23} + 2 q^{25} + 6 q^{29} + 5 q^{31} -5 q^{37} + ( -4 + 8 \zeta_{6} ) q^{41} + ( -2 + 4 \zeta_{6} ) q^{43} -3 q^{47} + 9 q^{53} -3 q^{55} -9 q^{59} + ( -5 + 10 \zeta_{6} ) q^{61} + ( 3 - 6 \zeta_{6} ) q^{67} + ( -2 + 4 \zeta_{6} ) q^{71} + ( 1 - 2 \zeta_{6} ) q^{73} + ( 3 - 6 \zeta_{6} ) q^{79} -12 q^{83} -9 q^{85} + ( -7 + 14 \zeta_{6} ) q^{89} + ( 7 - 14 \zeta_{6} ) q^{95} + ( 4 - 8 \zeta_{6} ) q^{97} +O(q^{100})$$ $$\operatorname{Tr}(f)(q)$$ $$=$$ $$2q + O(q^{10})$$ $$2q + 14q^{19} + 4q^{25} + 12q^{29} + 10q^{31} - 10q^{37} - 6q^{47} + 18q^{53} - 6q^{55} - 18q^{59} - 24q^{83} - 18q^{85} + O(q^{100})$$

## Character values

We give the values of $$\chi$$ on generators for $$\left(\mathbb{Z}/7056\mathbb{Z}\right)^\times$$.

 $$n$$ $$785$$ $$1765$$ $$4609$$ $$6175$$ $$\chi(n)$$ $$1$$ $$1$$ $$-1$$ $$-1$$

## Embeddings

For each embedding $$\iota_m$$ of the coefficient field, the values $$\iota_m(a_n)$$ are shown below.

For more information on an embedded modular form you can click on its label.

Label $$\iota_m(\nu)$$ $$a_{2}$$ $$a_{3}$$ $$a_{4}$$ $$a_{5}$$ $$a_{6}$$ $$a_{7}$$ $$a_{8}$$ $$a_{9}$$ $$a_{10}$$
1567.1
 0.5 + 0.866025i 0.5 − 0.866025i
0 0 0 1.73205i 0 0 0 0 0
1567.2 0 0 0 1.73205i 0 0 0 0 0
 $$n$$: e.g. 2-40 or 990-1000 Significant digits: Format: Complex embeddings Normalized embeddings Satake parameters Satake angles

## Inner twists

Char Parity Ord Mult Type
1.a even 1 1 trivial
28.d even 2 1 inner

## Twists

By twisting character orbit
Char Parity Ord Mult Type Twist Min Dim
1.a even 1 1 trivial 7056.2.b.m 2
3.b odd 2 1 784.2.f.b 2
4.b odd 2 1 7056.2.b.b 2
7.b odd 2 1 7056.2.b.b 2
7.c even 3 1 1008.2.cs.f 2
7.d odd 6 1 1008.2.cs.c 2
12.b even 2 1 784.2.f.a 2
21.c even 2 1 784.2.f.a 2
21.g even 6 1 112.2.p.b yes 2
21.g even 6 1 784.2.p.d 2
21.h odd 6 1 112.2.p.a 2
21.h odd 6 1 784.2.p.c 2
24.f even 2 1 3136.2.f.b 2
24.h odd 2 1 3136.2.f.a 2
28.d even 2 1 inner 7056.2.b.m 2
28.f even 6 1 1008.2.cs.f 2
28.g odd 6 1 1008.2.cs.c 2
84.h odd 2 1 784.2.f.b 2
84.j odd 6 1 112.2.p.a 2
84.j odd 6 1 784.2.p.c 2
84.n even 6 1 112.2.p.b yes 2
84.n even 6 1 784.2.p.d 2
168.e odd 2 1 3136.2.f.a 2
168.i even 2 1 3136.2.f.b 2
168.s odd 6 1 448.2.p.b 2
168.v even 6 1 448.2.p.a 2
168.ba even 6 1 448.2.p.a 2
168.be odd 6 1 448.2.p.b 2

By twisted newform orbit
Twist Min Dim Char Parity Ord Mult Type
112.2.p.a 2 21.h odd 6 1
112.2.p.a 2 84.j odd 6 1
112.2.p.b yes 2 21.g even 6 1
112.2.p.b yes 2 84.n even 6 1
448.2.p.a 2 168.v even 6 1
448.2.p.a 2 168.ba even 6 1
448.2.p.b 2 168.s odd 6 1
448.2.p.b 2 168.be odd 6 1
784.2.f.a 2 12.b even 2 1
784.2.f.a 2 21.c even 2 1
784.2.f.b 2 3.b odd 2 1
784.2.f.b 2 84.h odd 2 1
784.2.p.c 2 21.h odd 6 1
784.2.p.c 2 84.j odd 6 1
784.2.p.d 2 21.g even 6 1
784.2.p.d 2 84.n even 6 1
1008.2.cs.c 2 7.d odd 6 1
1008.2.cs.c 2 28.g odd 6 1
1008.2.cs.f 2 7.c even 3 1
1008.2.cs.f 2 28.f even 6 1
3136.2.f.a 2 24.h odd 2 1
3136.2.f.a 2 168.e odd 2 1
3136.2.f.b 2 24.f even 2 1
3136.2.f.b 2 168.i even 2 1
7056.2.b.b 2 4.b odd 2 1
7056.2.b.b 2 7.b odd 2 1
7056.2.b.m 2 1.a even 1 1 trivial
7056.2.b.m 2 28.d even 2 1 inner

## Hecke kernels

This newform subspace can be constructed as the intersection of the kernels of the following linear operators acting on $$S_{2}^{\mathrm{new}}(7056, [\chi])$$:

 $$T_{5}^{2} + 3$$ $$T_{11}^{2} + 3$$ $$T_{13}$$ $$T_{17}^{2} + 27$$ $$T_{19} - 7$$ $$T_{31} - 5$$ $$T_{53} - 9$$

## Hecke characteristic polynomials

$p$ $F_p(T)$
$2$ 1
$3$ 1
$5$ $$1 - 7 T^{2} + 25 T^{4}$$
$7$ 1
$11$ $$1 - 19 T^{2} + 121 T^{4}$$
$13$ $$( 1 - 13 T^{2} )^{2}$$
$17$ $$1 - 7 T^{2} + 289 T^{4}$$
$19$ $$( 1 - 7 T + 19 T^{2} )^{2}$$
$23$ $$1 + 29 T^{2} + 529 T^{4}$$
$29$ $$( 1 - 6 T + 29 T^{2} )^{2}$$
$31$ $$( 1 - 5 T + 31 T^{2} )^{2}$$
$37$ $$( 1 + 5 T + 37 T^{2} )^{2}$$
$41$ $$1 - 34 T^{2} + 1681 T^{4}$$
$43$ $$1 - 74 T^{2} + 1849 T^{4}$$
$47$ $$( 1 + 3 T + 47 T^{2} )^{2}$$
$53$ $$( 1 - 9 T + 53 T^{2} )^{2}$$
$59$ $$( 1 + 9 T + 59 T^{2} )^{2}$$
$61$ $$( 1 - 13 T + 61 T^{2} )( 1 + 13 T + 61 T^{2} )$$
$67$ $$1 - 107 T^{2} + 4489 T^{4}$$
$71$ $$1 - 130 T^{2} + 5041 T^{4}$$
$73$ $$( 1 - 17 T + 73 T^{2} )( 1 + 17 T + 73 T^{2} )$$
$79$ $$( 1 - 17 T + 79 T^{2} )( 1 + 17 T + 79 T^{2} )$$
$83$ $$( 1 + 12 T + 83 T^{2} )^{2}$$
$89$ $$1 - 31 T^{2} + 7921 T^{4}$$
$97$ $$1 - 146 T^{2} + 9409 T^{4}$$


text:
# Baseband signal quantizer estimation

Imported: 17 Feb '17 | Published: 23 Sep '14

USPTO - Utility Patents

## Abstract

A method of deblocking an input signal is disclosed. The method generally includes the steps of (A) calculating a plurality of transform coefficients corresponding to each of a plurality of blocks in the input signal at baseband, (B) calculating a plurality of quantization parameters based on the transform coefficients, at least one of the quantization parameters corresponding to each respective one of the blocks and (C) generating an output signal by deblocking the input signal based on the quantization parameters.

## Description

This is a divisional of U.S. Ser. No. 11/947,037, filed Nov. 29, 2007 now U.S. Pat. No. 8,150,187, which is incorporated by reference.

### FIELD OF THE INVENTION

The present invention relates to signal quality improvements generally and, more particularly, to a method and/or apparatus for implementing a baseband signal quantizer estimation.

### BACKGROUND OF THE INVENTION

Estimating a “quality” of a baseband video (i.e., frames and/or fields and/or sub-portions of frames/fields) or images or audio signals (i.e., pixel domains, not bitstreams) that may have been previously compressed and then subsequently decompressed using transformed-based techniques is difficult. Further difficulties arise in estimating what quantizer or maximum quantizer was applied to the video/image/audio signals if the baseband signals were previously compressed and then decompressed in multiple previous generations. The absence of compression information in the baseband signals leaves the blockiness of the video/image signals and the amount of mosquito noise (i.e., Gibbs artifacts) in video/image signals hard to estimate quantitatively.

Existing techniques to estimate the quantizer qualities and/or quantities from baseband signals use comparisons of pixels and/or sample differences at different regular intervals (i.e., modulo the suspected transform-size) in a pixel/sample domain. However, the existing techniques are easily confused by edges existing in the content itself. Therefore, the existing techniques are inaccurate. Furthermore, the existing techniques are incapable of providing any kind of accurate estimation of quantizer values, let alone accurate tracking of the quantizer values over time as rate-control varies the quantizer values while compressing. A practical disadvantage is that if the estimated quality (i.e., blockiness/quantizer/quality) is used for processing of the baseband signal, then poor results are commonly obtained.

### SUMMARY OF THE INVENTION

The present invention concerns a method of deblocking an input signal. The method generally comprises the steps of (A) calculating a plurality of transform coefficients corresponding to each of a plurality of blocks in the input signal at baseband, (B) calculating a plurality of quantization parameters based on the transform coefficients, at least one of the quantization parameters corresponding to each respective one of the blocks and (C) generating an output signal by deblocking the input signal based on the quantization parameters.

The objects, features and advantages of the present invention include providing a baseband signal quantizer estimation that may (i) provide deblocking of a baseband signal, (ii) extract forensic information from the baseband signal, (iii) provide noise filtering of the baseband signal, (iv) enable accurate application of a variable deblocking strength and/or (v) operate on several channels of the baseband video signal independently.

### DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention generally provides baseband signal quantizer estimations for video, still images and/or audio signals. The resulting quantization parameter (QP) information may be used in pre-processing and/or post-processing of the baseband signals for deblocking, mosquito noise removal and/or sharpening. Forensic analysis of the baseband signals may be based on the quantization parameters QP to determine information about the history of the processing applied to the signal. Watermark extraction may be enabled by using information about the compression applied to accurately determine the present/absence of a watermark for purposes of copyright enforcement. Furthermore, the forensic analysis may be used to detect patent infringement, certifying data path integrity, certifying quality guarantees and/or for determining data authenticity.

Accurate tracking of the quantization parameters QP generally enables strong deblocking near events that cause large increases in the video quantization parameters QP (e.g., scene changes, camera flashes, etc.) while accurately using weak deblocking for sections of the video that use relatively smaller quantization parameters QP. The present invention may be applicable to, but is not limited to, MPEG-2 video, MPEG-4 Part 2 video, DV video, JPEG images, AAC audio, MP3 audio and other signals using transform-based compressions and decompressions. Potential implementations include, but are not limited to, professional encoding equipment, consumer equipment and transcoders.

The following examples generally assume an 8×8 grid having a position known a priori. The examples generally consider the luminance components of signals, but may be applied to the chrominance components as well. The estimated quantization parameters QP may be used to drive a deblocker, noise filter, forensic function and/or other signal processing operations.

Referring to FIG. 1, a flow diagram of a conventional MPEG-2 coding is shown. An MPEG-2 transform coding generally works by transforming a block of time domain samples (e.g., f) into multiple Discrete Cosine Transform (DCT) coefficients (e.g., F). The DCT coefficients may then be quantized (Q) to create quantized DCT coefficients (e.g., QF). The quantized DCT coefficients may then be entropy coded to generate a bitstream. The relation between each of the AC coefficients among the DCT coefficients (the DC coefficient is quantized differently) and the respective quantized versions QF may be given by equation 1 as follows:

$QF = F w  qscale 16 Eq .  ( 1 )$
where “w” may be the weight corresponding to the AC DCT coefficient in the quantization matrix and “qscale” may be the quantization parameter, also referred to as “QP” for short.

Referring to FIG. 2, a flow diagram of a conventional MPEG-2 decoding is shown. An MPEG-2 transform decoding generally works by entropy decoding the bitstream to recover the quantized DCT coefficients QF. An inverse quantization (iQ) may then be used to generate an estimated version of the DCT coefficients (e.g., F′). An inverse DCT transformation (iDCT) generally converts the DCT coefficients into an estimated version of the original block of time domain samples (e.g., f′). The quantization parameter QP is generally a good estimate of the amount of blockiness in the video.

The quantization parameter QP may be calculated from the estimated DCT coefficients F′. For example, the three lowest frequency AC coefficients (e.g., a first horizontal coefficient, a vertical coefficient and a diagonal coefficient) may be used to in calculating the quantization parameter QP. Corresponding weights w of the three lowest AC coefficients in a default MPEG-2 quantization matrix may each be 16. Equation 1 therefore becomes equation 2 as follows:

$QF = F qscale Eq .  ( 2 )$
The decoding process generally uses equation 3 to calculate F′ from QF, as follows:
F′=QF×qscale  Eq. (3)

Assuming a baseband video signal originates from a decoded MPEG-2 content, the following are generally true (i) the DCT may be based on 8×8 blocks, (ii) the quantization parameter QP may be constant, at least for the 4 luminance blocks inside a macroblock, and (iii) at least 3 low frequency AC DCT coefficients exist in each of the 8×8 blocks. For a given intra-coded macroblock, multiple equations (e.g., 12 equations) may exist as shown in equation 4 as follows:
F′ij=(QF)ij×qscale  Eq. (4)
where 1≦i≦4 may denote the ith block within the macroblock under consideration and 1≦j≦3 may denote horizontal, vertical, and diagonal low frequency AC DCT coefficient for block i. Assuming a baseband video that is aligned with the grid, the estimated DCT coefficients F′ij may be computed from the time domain samples f′ij per equations 5 thru 7 as follows:

$F i   1 ′ = 1 4  1 2  1 2  ∑ x = 0 7  ∑ y = 0 7  f i ′  ( x , y )  cos  ( 2  y + 1 )  π 16 Eq .  ( 5 ) F i   2 ′ = 1 4  1 2  1 2  ∑ x = 0 7  ∑ y = 0 7  f i ′  ( x , y )  cos  ( 2  x + 1 )  π 16 Eq .  ( 6 ) F i   3 ′ = 1 4  ∑ x = 0 7  ∑ y = 0 7  f i ′  ( x , y )  cos  ( 2  x + 1 )  π 16  cos  ( 2  y + 1 )  π 16 Eq .  ( 7 )$
Any of the above 12 equations alone generally cannot be used to “reverse-engineer” the quantization parameter QP, since recovery of QFij may not be possible. However, by looking at the 12 equations collectively, an estimation may be performed to calculate what the quantization QP might have been. Having more than 12 equations per macroblock may result in even a better estimation. Such an estimation may be possible if the quantization parameter QP is assumed not to change from one macroblock to the next macroblock.

Referring to FIG. 3, a histogram 100 of first example positive estimated DCT coefficients in an Intra-coded frame (I-frame) having a constant quantization parameter QP of 24 is shown. The histogram generally peaks at multiples of the quantization parameter QP. A highest peak may occur at a first quantization level.

Referring to FIG. 4, a histogram 110 of second example positive estimated DCT coefficients in an I-frame having an average quantization parameter QP of 16 is shown. In practice, the quantization parameter QP may not be fixed for a whole frame. However, a high peak corresponding to an average quantization parameter QP generally exists around the first (or initial) quantization level. Furthermore, the peak at the first quantization level is usually the biggest within the histogram. FIG. 4 generally shows the histogram of a positive F′ij for the same I-frame as in FIG. 3 coded without forcing the quantization parameter QP to a single value. In FIG. 4, the average quantization parameter QP for the frame is 16. The histogram shows that first peak may be very close to 16. As such, the location of the first histogram peak may be used as an estimate for the underlying quantization parameter QP value.

Referring to FIG. 5, a diagram of an example block 120 is shown. An estimation of the quantization parameter QP may be made from a 4×4 matrix of the four DC values of the block 120. Considering the four 4×4 blocks of the block 120, where each square may represent a pixel sample, let Si for 1≦i≦4 be a sum of absolute differences in the ith 4×4 sub-block. Therefore, equations 8 thru 10 may be used to calculate the estimated DCT coefficients F′ij as follows:

$F i   1 ′ ≈ 1 8  ( S 1 + S 2 ) - ( S 3 + S 4 ) Eq .  ( 8 ) F 12 ′ ≈ 1 8  ( S 1 + S 3 ) - ( S 2 + S 4 ) Eq .  ( 9 ) F i   3 ′ ≈ 1 4  ( S 1 + S 4 ) - ( S 2 + S 3 ) Eq .  ( 10 )$
The above equations may be rearranged in two ways so that some of the additions may be “reused”, thus saving some processing cycles, as equations 11 thru 13 as follows:

$F i   1 ′ ≈ 1 8  ( S 1 - S 4 ) + ( S 2 - S 3 ) Eq .  ( 11 ) F i   2 ′ ≈ 1 8  ( S 1 - S 4 ) + ( S 3 - S 2 ) = 1 8  ( S 1 - S 4 ) - ( S 2 - S 3 ) Eq .  ( 12 ) F i   3 ′ ≈ 1 4  ( S 1 + S 4 ) - ( S 2 + S 3 ) Eq .  ( 13 )$
By eliminating the coefficients F′i3, an estimate of the four DC values may be calculated using only three subtractions and one addition. The approximations effectively model the cosine with a Haar-like basis function (e.g., the cosine may be approximated with 1 whenever positive, and −1 whenever negative).

Referring to FIG. 6, a histogram 130 of third example positive estimated DCT coefficients for the I-frame of FIG. 4 is shown. The histogram only uses the estimated DCT coefficient F′i1 and F′i2. Using only some of the estimated DCT coefficients generally produces lower counts in the histogram. For example, the first peak may slightly underestimate the average quantization parameter QP of 16, which may be compensated.

Referring to FIG. 7, a block diagram of an example implementation of an apparatus 140 in accordance with a preferred embodiment of the present invention is shown. The apparatus (or system) 140 may be used to implement the techniques of the present invention as disclosed above. The apparatus 140 generally comprises a circuit (or module) 142, a circuit (or module) 144 and an optional circuit (or module) 146. An input signal (e.g., IN) may be received by the circuit 142 and the circuit 144. An intermediate signal (e.g., INT) may be presented from circuit 142 to the circuit 144. The circuit 144 may generate and present an output signal (e.g., OUT). In some embodiments, a forensic signal (e.g., FOR) may be presented from the circuit 144 to the circuit 146.

The circuit 142 generally implements a quantization parameter estimation operation. The circuit 142 may be operational to estimate (calculate) one or more quantization parameter QP values based on the signal IN. The quantization parameter QP values may be carried in the signal INT to the circuit 144.

The circuit 144 may implement a signal processor. The circuit 144 is generally operational to process the signal IN based on the quantization parameters QP received in the signal INT to generate the signal OUT. The processing may include, but is not limited to, deblocking, noise filtering and/or forensic analysis. In embodiments generating forensic data, the circuit 144 may be operational to transmit the forensic information in the signal FOR to the circuit 146.

The circuit 146 may implement a storage medium. The circuit 146 may be operational to store the forensic data received in the signal FOR to enable subsequent playback and further analysis. The circuit 146 may be implemented as a magnetic, solid state and/or optical storage medium. Other storage technologies may be implemented to meet the criteria of a particular application.

The signal IN may implement a digital video signal, a digital still image signal or a digital audio signal. The signal IN may be received by the circuit 142 and the circuit 144 as a baseband signal. A previous transform-based compression and later decompression of the signal IN may have taken place prior to reception by the apparatus 140.

The signal OUT may also be implemented as the digital video signal, the digital still image or the digital audio signal. The signal OUT may be a processed version of the signal IN. The processing is generally based on the quantization parameters QP extracted from the signal IN by the circuit 142.

Referring to FIG. 8, a detailed block diagram of an example implementation of the circuit 142 is shown. The circuit 142 generally comprises a circuit (or module) 150 and a circuit (or module 152). The module 150 may receive the signal IN. An estimated transform coefficient signal (e.g., TC) may be generated and presented from the circuit 150 to the circuit 152. A signal (e.g., SIZE) may be generated and presented from the circuit 150 to the circuit 152. A signal (e.g., OFFSET) may also be generated and presented from the circuit 150 to the circuit 152. The signal INT may be generated and presented from the circuit 152.

The circuit 150 may be operational to estimate the transform coefficients from the signal IN. The transform coefficients may be based on a fixed block size in known locations. Estimating the transform coefficients may be based on one or more of the following: (i) using block average differences of the baseband signal (e.g., a Hardamard transform), (ii) two or more of the lowest frequency AC coefficients, (iii) using one or more gaps between two peaks in a coefficient histogram, (iv) using a gap between the origin and the initial peak (or a subsequent peak) in the coefficient histogram and (v) using histograms of 4×4 DC block differences. The lowest AC coefficients are generally the most accurate for low bitrate signals that may not contain many high-frequency coefficients (e.g., the high frequency coefficients may have been quantized to zero.)

The coefficient estimations may also be used to determine a block-grid alignment and/or blockiness of the signal by estimating over multiple different options (e.g., different block sizes and different block offsets) and determining which option yields the best separated histogram (e.g., the histogram with the highest peaks and/or the best separation between peaks.) The varying block sizes may be reported in the signal SIZE with reporting the respective transform coefficients in the signal TC. In one or more embodiments, the circuit 150 may also be operational to calculate an offset of the blocks from a standard location. The block offsets may be reported in the signal OFFSET along with the reporting of the respective transform coefficients. While the embodiments generally describe estimations based on the luminance components of the signal, the estimations may also be applied to both chrominance channels (e.g., U and V). In some embodiments, (e.g., an H.264 compressed/decompressed signal) may permit the use of a quantization parameter QP offset between the chrominance channels and the luminance channel.

The circuit 152 may be operational to calculate the estimated quantization parameters QP based on the transform coefficients, the one or more block sizes and the offset, if applicable. For each macroblock, up to 12 transform coefficients may be considered in the calculations. The estimated quantization parameters QP may be presented to the circuit 144 in the intermediate signal INT.

Referring to FIG. 9, a flow diagram of an example method 160 of analyzing the baseband signal IN is shown. The method (or process) 160 may be implemented by the apparatus 140. The method 160 generally comprises a step (or block) 162, a step (or block) 164, a step (or block) 166, a step (or block) 168, a step (or block) 170, a step (or block) 172, a step (or block) 174, a step (or block) 176, a step (or block) 178 and a step (or block) 180.

In the step 162, the signal IN may be parsed into a luminance channel and multiple (e.g., 2) chrominance channels by the circuit 150. The circuit 150 may examine the luminance channel of the signal IN to determine one or more luminance transform coefficients (e.g., TCL) in the step 164. In the step 166, the circuit 152 may calculate a quantization parameter (e.g., QPL) for the luminance channel. The luminance quantization parameter QPL may be presented to the circuit 144 for further processing in the step 168. The processed luminance channel may be presented in a signal (e.g., OUTL).

In the step 170, the circuit 150 (or a copy of the circuit 150) may examine a first chrominance channel of the signal IN to determine one or more chrominance transform coefficients (e.g., TCC1). In the step 172, the circuit 152 (or a copy of the circuit 152) may calculate a quantization parameter (e.g., QPC1) for the first chrominance channel. The first chrominance channel quantization parameter QPC1 may be presented to the circuit 144 for further processing in the step 174. The processed first chrominance channel may be presented in a signal (e.g., OUTC1).

In the step 176, the circuit 150 (or a copy of the circuit 150) may examine a second chrominance channel of the signal IN to determine one or more chrominance transform coefficients (e.g., TCC2). In the step 178, the circuit 152 (or a copy of the circuit 152) may calculate a quantization parameter (e.g., QPC2) for the second chrominance channel. The second chrominance channel quantization parameter QPC2 may be presented to the circuit 144 for further processing in the step 180. The processed second chrominance channel may be presented in a signal (e.g., OUTC2).

Referring to FIG. 10, a flow diagram of an example method 200 to determine a best block size and a best offset is shown. The method (or process) 200 may be implemented by the apparatus 140. The method 200 generally comprises a step (or block) 202, a step (or block) 204, a step (or block) 206, a step (or block) 208, a step (or block) 210, a step (or block) 212, a step (or block) 214, a step (or block) 216 and a step (or block) 218.

In the step 202, the apparatus 140 may initialize the process by setting (i) a current block size to an initial block size and (ii) a current block offset to an initial block offset from a reference grid. The circuit 142 may calculate a first set of transform coefficients corresponding to the current block size and the current block offset in the step 204. A check may be made by the circuit 142 in the step 206 to see if the resulting set of transform coefficients result in a best histogram. If the current histogram is a best histogram (e.g., the YES branch of step 206), the circuit 142 may store the current block size and the current block offset in the step 208.

If either the current histogram is the best histogram (e.g., the step 208) or a better histogram has already been stored (e.g., the NO branch of step 206), the circuit 142 may check for a next block offset. If another block offset is available to try (e.g., the YES branch of step 210), the method 200 may continue with estimating the transform coefficients in the step 204. Once all of the block offsets for a given block size have been checked (e.g., the NO branch of step 210), the method 200 may continue by checking additional block sizes.

If more block sizes are available to be checked (e.g., the YES branch of step 214), a next block size may be selected in the step 216. Once all of the block sizes have been tried (e.g., the NO branch of step 214), the circuit 142 may output the transform coefficient values, block size value and block offset value corresponding to the best histogram in the step 218.

The following Octave script may be used to simulate the above techniques. GNU Octave (http://www.octave.org) is open source code and is generally compatible with Mat-lab.

Q(Pest.m) = more off nChromaFormat = 420; sPath = ’../path/to/yuv/file/’; nWidth = 352; nHeight = 240; sFilename = ’seq.yuv’; sFilename = strcat( sPath, sFilename );  disp( sFilename ); mLuma = fYUVRead( sFilename, nWidth, nHeight, 0, 0, 420 ); %%%% DCT Histogram vResult = blkproc( mLuma, [8 8], ’fDCT’ ); vResult = vResult(:); vHist = tabulate( vResult(vResult>2 & vResult<200 ) ); figure; bar( vHist(:,1), vHist(:,2) ) %%%% Repeat for Haar Histogram vResult = blkproc( mLuma, [8 8], ’fHaar’ ); vResult = vResult(:); vHist = tabulate( vResult(vResult>2 & vResult<200 ) ); figure; bar( vHist(:,1), vHist(:,2) ) return Functions fDCT( ) and fHaar may be used in estimating Fij (fDCT.m) = function v = mydct( mBlock ); v = [ 0 0 0 ]; F = round( dct2( mBlock ) ); if F(1,2) v(1) = F(1,2); end if F(2,1) v(2) = F(2,1); end if F(2,2) v(3) = F(2,2); end return

The functions performed by the diagrams of FIGS. 1-10 may be implemented using a conventional general purpose digital computer programmed according to the teachings of the present specification, as will be apparent to those skilled in the relevant art(s). Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will also be apparent to those skilled in the relevant art(s).

The present invention may also be implemented by the preparation of ASICs, FPGAs, or by interconnecting an appropriate network of conventional component circuits, as is described herein, modifications of which will be readily apparent to those skilled in the art(s).

The present invention thus may also include a computer product which may be a storage medium including instructions which can be used to program a computer to perform a process in accordance with the present invention. The storage medium can include, but is not limited to, any type of disk including floppy disk, optical disk, CD-ROM, magneto-optical disks, ROMs, RAMS, EPROMs, EEPROMs, Flash memory, magnetic or optical cards, or any type of media suitable for storing electronic instructions.

While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the scope of the invention.

## Claims

1. A method of analyzing an input signal, comprising the steps of:
(A) calculating a plurality of transform coefficients corresponding to each of a plurality of blocks in said input signal at baseband;
(B) calculating a plurality of sizes of said blocks, wherein at least two of said sizes are different from each other;
(C) calculating a plurality of offsets of said blocks from a block grid;
(D) calculating a plurality of sets of said transform coefficients, one of said sets corresponding to each respective one of said sizes and a respective one of said offsets;
(E) calculating a plurality of histograms, one of said histograms corresponding to each respective one of said sets; and
(F) calculating a plurality of quantization parameters based on
(i) said transform coefficients,
(ii) said sizes
(iii) said offsets, and
(iv) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
at least one of said quantization parameters corresponding to each respective one of said blocks;
(G) a generating information by performing a forensic analysis on said input signal, wherein said information describes a previous transform-based compression and subsequent decompression of said input signal based on said quantization parameters; and
(H) storing said information in a nonvolatile memory.
(A) calculating a plurality of transform coefficients corresponding to each of a plurality of blocks in said input signal at baseband;
(B) calculating a plurality of sizes of said blocks, wherein at least two of said sizes are different from each other;
(C) calculating a plurality of offsets of said blocks from a block grid;
(D) calculating a plurality of sets of said transform coefficients, one of said sets corresponding to each respective one of said sizes and a respective one of said offsets;
(E) calculating a plurality of histograms, one of said histograms corresponding to each respective one of said sets; and
(F) calculating a plurality of quantization parameters based on
(i) said transform coefficients,
(ii) said sizes
(iii) said offsets, and
(iv) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
at least one of said quantization parameters corresponding to each respective one of said blocks;
(G) a generating information by performing a forensic analysis on said input signal, wherein said information describes a previous transform-based compression and subsequent decompression of said input signal based on said quantization parameters; and
(H) storing said information in a nonvolatile memory.
(i) said transform coefficients,
(ii) said sizes
(iii) said offsets, and
(iv) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
2. The method according to claim 1, wherein said calculating of said quantization parameters is based on a subset of said transform coefficients having a plurality of lowest frequency AC coefficients in each of said blocks.
3. The method according to claim 1, further comprising the step of:
generating a plurality of histograms of said transform coefficients, one of said histograms corresponding to each respective one of a predetermined grouping of said blocks.
generating a plurality of histograms of said transform coefficients, one of said histograms corresponding to each respective one of a predetermined grouping of said blocks.
4. The method according to claim 3, wherein said calculating of said quantization parameters is further based on a plurality of gaps in said histograms, one of said gaps corresponding to each respective one of said histograms.
5. The method according to claim 4, where (i) each of said gaps is measured between a first peak in said respective histogram and a second peak in said respective histogram (ii) and each of said first peaks and said second peaks is offset from an origin of said respective histogram.
6. The method according to claim 4, wherein each of said gaps is measured between an origin of said respective histogram and an initial peak in said respective histogram.
7. The method according to claim 1, wherein said information includes at least one of said quantization parameters used in said previous transform-based compression.
8. The method according to claim 1, wherein said input signal is one of (i) a still image and (ii) an audio signal.
9. The method according to claim 1, wherein said information includes at least one bit rate used in said previous transform-based compression.
10. The method according to claim 1, wherein said information includes at least one of said sizes of said blocks used in said previous transform-based compression.
11. The method according to claim 1, wherein said information is a basis to one or more of (i) a certification of data path integrity, (ii) a certification of quality guarantees and (iii) a determination of data authenticity.
12. An apparatus comprising:
a first circuit configured to
(i) calculate a plurality of transform coefficients corresponding to each of a plurality of blocks in an input signal at baseband,
(ii) calculate a plurality of sizes of said blocks,
wherein at least two of said sizes are different from each other,
(iii) calculate a plurality of offsets of said blocks from a block grid,
(iv) calculate a plurality of sets of said transform coefficients, one of said sets corresponding to each respective one of said sizes and a respective one of said offsets,
(v) calculate a plurality of histograms, one of said histograms corresponding to each respective one of said sets and
(vi) calculate a plurality of quantization parameters based on
(a) said transform coefficients,
(b) said sizes
(c) said offsets, and
(d) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
at least one of said quantization parameters corresponding to each respective one of said blocks; and
a second circuit configured to
(i) generate information by performing a forensic analysis on said input signal,
wherein said information describes a previous transform-based compression and subsequent decompression of said input signal based on said quantization parameters, and
(ii) store said information in a nonvolatile memory.
a first circuit configured to
(i) calculate a plurality of transform coefficients corresponding to each of a plurality of blocks in an input signal at baseband,
(ii) calculate a plurality of sizes of said blocks,
wherein at least two of said sizes are different from each other,
(iii) calculate a plurality of offsets of said blocks from a block grid,
(iv) calculate a plurality of sets of said transform coefficients, one of said sets corresponding to each respective one of said sizes and a respective one of said offsets,
(v) calculate a plurality of histograms, one of said histograms corresponding to each respective one of said sets and
(vi) calculate a plurality of quantization parameters based on
(a) said transform coefficients,
(b) said sizes
(c) said offsets, and
(d) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
at least one of said quantization parameters corresponding to each respective one of said blocks; and
(a) said transform coefficients,
(b) said sizes
(c) said offsets, and
(d) a particular one of said histograms having a widest separation between two peaks as compared to other peaks in said histograms,
(i) generate information by performing a forensic analysis on said input signal,
wherein said information describes a previous transform-based compression and subsequent decompression of said input signal based on said quantization parameters, and
(ii) store said information in a nonvolatile memory.
13. The apparatus according to claim 12, wherein said calculation of said quantization parameters is based on a subset of said transform coefficients having a plurality of lowest frequency AC coefficients in each of said blocks.
14. The apparatus according to claim 12, wherein said information includes at least one bit rate used in said previous transform-based compression.
15. The apparatus according to claim 12, wherein said information includes at least one of said sizes of said blocks used in said previous transform-based compression.


text:
# Energy Carried by Electromagnetic Waves

## LEARNING OBJECTIVES

By the end of this section, you will be able to:

• Express the time-averaged energy density of electromagnetic waves in terms of their electric and magnetic field amplitudes
• Calculate the Poynting vector and the energy intensity of electromagnetic waves
• Explain how the energy of an electromagnetic wave depends on its amplitude, whereas the energy of a photon is proportional to its frequency

Anyone who has used a microwave oven knows there is energy in electromagnetic waves. Sometimes this energy is obvious, such as in the warmth of the summer Sun. Other times, it is subtle, such as the unfelt energy of gamma rays, which can destroy living cells.

Electromagnetic waves bring energy into a system by virtue of their electric and magnetic fields. These fields can exert forces and move charges in the system and, thus, do work on them. However, there is energy in an electromagnetic wave itself, whether it is absorbed or not. Once created, the fields carry energy away from a source. If some energy is later absorbed, the field strengths are diminished and anything left travels on.

Clearly, the larger the strength of the electric and magnetic fields, the more work they can do and the greater the energy the electromagnetic wave carries. In electromagnetic waves, the amplitude is the maximum field strength of the electric and magnetic fields (Figure 13.3.1). The wave energy is determined by the wave amplitude.

(Figure 13.3.1)

For a plane wave traveling in the direction of the positive x-axis with the phase of the wave chosen so that the wave maximum is at the origin at

the electric and magnetic fields obey the equations

The energy in any part of the electromagnetic wave is the sum of the energies of the electric and magnetic fields. This energy per unit volume, or energy density

is the sum of the energy density from the electric field and the energy density from the magnetic field. Expressions for both field energy densities were discussed earlier (

in Capacitance and

in Inductance). Combining these the contributions, we obtain

The expression

then shows that the magnetic energy density

and electric energy density

are equal, despite the fact that changing electric fields generally produce only small magnetic fields. The equality of the electric and magnetic energy densities leads to

(13.3.1)

The energy density moves with the electric and magnetic fields in a similar manner to the waves themselves.

We can find the rate of transport of energy by considering a small time interval

As shown in Figure 13.3.2, the energy contained in a cylinder of length

and cross-sectional area

passes through the cross-sectional plane in the interval

(Figure 13.3.2)

The energy passing through area

in time

is

The energy per unit area per unit time passing through a plane perpendicular to the wave, called the energy flux and denoted by

can be calculated by dividing the energy by the area

and the time interval

More generally, the flux of energy through any surface also depends on the orientation of the surface. To take the direction into account, we introduce a vector

, called the Poynting vector, with the following definition:

(13.3.2)

The cross-product of

and

points in the direction perpendicular to both vectors. To confirm that the direction of

is that of wave propagation, and not its negative, return to Figure 13.2.2. Note that Lenz’s and Faraday’s laws imply that when the magnetic field shown is increasing in time, the electric field is greater at

than at

The electric field is decreasing with increasing

at the given time and location. The proportionality between electric and magnetic fields requires the electric field to increase in time along with the magnetic field. This is possible only if the wave is propagating to the right in the diagram, in which case, the relative orientations show that

is specifically in the direction of propagation of the electromagnetic wave.

The energy flux at any place also varies in time, as can be seen by substituting

from Equation 13.2.11 into Equation 13.3.1.

(13.3.3)

Because the frequency of visible light is very high, of the order of

the energy flux for visible light through any area is an extremely rapidly varying quantity. Most measuring devices, including our eyes, detect only an average over many cycles. The time average of the energy flux is the intensity

of the electromagnetic wave and is the power per unit area. It can be expressed by averaging the cosine function in Equation 13.3.3 over one complete cycle, which is the same as time-averaging over many cycles (here,

is one period):

(13.3.4)

We can either evaluate the integral, or else note that because the sine and cosine differ merely in phase, the average over a complete cycle for

is the same as for

to obtain

where the angle brackets

stand for the time-averaging operation. The intensity of light moving at speed

in vacuum is then found to be

(13.3.5)

in terms of the maximum electric field strength

which is also the electric field amplitude. Algebraic manipulation produces the relationship

(13.3.6)

where

is the magnetic field amplitude, which is the same as the maximum magnetic field strength. One more expression for

in terms of both electric and magnetic field strengths is useful. Substituting the fact that

the previous expression becomes

(13.3.7)

We can use whichever of the three preceding equations is most convenient, because the three equations are really just different versions of the same result: The energy in a wave is related to amplitude squared. Furthermore, because these equations are based on the assumption that the electromagnetic waves are sinusoidal, the peak intensity is twice the average intensity; that is,

## EXAMPLE 13.3.1

#### A Laser Beam

The beam from a small laboratory laser typically has an intensity of about

Assuming that the beam is composed of plane waves, calculate the amplitudes of the electric and magnetic fields in the beam.

#### Strategy

Use the equation expressing intensity in terms of electric field to calculate the electric field from the intensity.

#### Solution

From Equation 13.3.5, the intensity of the laser beam is

The amplitude of the electric field is therefore

The amplitude of the magnetic field can be obtained from Equation 13.2.8:

## EXAMPLE 13.3.2

#### Light Bulb Fields

A light bulb emits

of power as visible light. What are the average electric and magnetic fields from the light at a distance of

?

#### Strategy

Assume the bulb’s power output

is distributed uniformly over a sphere of radius

to calculate the intensity, and from it, the electric field.

#### Solution

The power radiated as visible light is then

#### Significance

The intensity

falls off as the distance squared if the radiation is dispersed uniformly in all directions.

## EXAMPLE 13.3.3

A

radio transmitter on Earth sends its signal to a satellite

away (Figure 13.3.3). At what distance in the same direction would the signal have the same maximum field strength if the transmitter’s output power were increased to

?

(Figure 13.3.3)

#### Strategy

The area over which the power in a particular direction is dispersed increases as distance squared, as illustrated in the figure. Change the power output

by a factor of (

) and change the area by the same factor to keep

the same.

Then use the proportion of area

in the diagram to distance squared to find the distance that produces the calculated change in area.

#### Solution

Using the proportionality of the areas to the squares of the distances, and solving, we obtain from the diagram

#### Significance

The range of a radio signal is the maximum distance between the transmitter and receiver that allows for normal operation. In the absence of complications such as reflections from obstacles, the intensity follows an inverse square law, and doubling the range would require multiplying the power by four.


text:
# Numerator Modulo 2011

Suppose $\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{2010} = \dfrac{m}{n}$ for some coprime positive integers $m, n.$ Find the remainder when $m$ is divided by $2011$.

×

Problem Loading...

Note Loading...

Set Loading...


text:
# Favorite Proof?

1. Jan 25, 2009

### harvellt

I am still a little early in my math education but we were talking about this the other day.
Mine is the right angle proof of the derivatives of inverse trig functions. The first time I went threw them I was just given the rule that the derivative of arcsin is such and such, with no real explanation. It was hard to remember and didn't make a lot of sense but after I took the time to look at the very simple proof it all beautifully clicked together.
What are yours?

2. Jan 25, 2009

### quasar987

This one is fine. First, try to think up for a while of a function f:R-->R that is nowhere locally bounded. That is to say, such that for any point a and any interval I however small around a , f is unbounded on I.

Then consider the following solution.

The function f given by

f(x)=0 if x is irrational and f(x)=n if x is rational and x=m/n where the fraction is reduced and n>0

has the desired property. To see this, consider a in R and e>0 and suppose f is bounded in (a-e,a+e). This would mean that the denominators (in reduced form) of all rational numbers in (a-e,a+e) are bounded. And since the interval (a-e,a+e) itself is bounded, this implies that the numerators are bounded too! But then this would mean that there are only finitely many rationals in (a-e,a+e), which is absurd.

3. Jan 26, 2009

### deiki

Hölder inequality.

4. Jan 27, 2009

### Enjoicube

I have just begun analysis, so all of my favorite proofs are very simple, but I love the proof that R is uncountable, and yet that any open interval within it is also uncountable. I am sure this will change with time though.

5. Jan 27, 2009

### uman

The proof of Lagrange's theorem: If H is a subgroup of G, the order of G is divisible by the order of H. It seems to go from a lot of simple ideas arranged into good definitions to a deep result, almost by magic.

6. Jan 27, 2009

### Kurret

The (two) proof(s) of Pythagoras Theorem which involves creating a square with sides equal to the hypothenuse, and then creating 4 equal triangles on the inside(outside) of the square with the sides being the hypothenuses. Very elegant, maybe not my favorite but the first that came to my mind right now.

7. Jan 27, 2009

### uman

I also really like the proof that the Cantor set (which has measure zero) has the same number of elements as the set of all real numbers. Just more evidence that real numbers are counterintuitive and bizarre!

8. Jan 27, 2009

### slider142

Some of my favourite theorems have already been listed. I'll add Stokes's Theorem for elegance and physical applications.

9. Jan 27, 2009

### uman

Which are your favorites that have already been mentioned, slider?

10. Jan 28, 2009

### Enjoicube

I always thought Greens theorem's proof was more beautiful than Stokes' theorem, even htough it is just a special case. Nevertheless, both are very beautiful, and Stokes is a close second in vector calc. The only proofs I can say I don't like are proof by cases when a direct proof would do, it's like whacking a lock off a door intead of using the key under the mat.

11. May 9, 2009

### Kurret

Just had to post about these proofs, which is two of my favorites
Proof of Fermats little theorem, from "problem solving strategies" by Arthur Engel:
Consider necklaces of p pears in a different colors where p is a prime number. We want to count the number of necklaces that does not only have all pearls in one color. So we start with a string of p pearls. there are a^p such strings. Now we connect ends and throw away the one colored necklaces, and we are left with a^p-a. But each necklaces now come in p copies, so the number we are looking for is (a^p-a)/p. Now this must be an integer, thus p|a^p-a.

Another proof I think is very elegant is a proof of Ptolemys theorem. Can be found at page 37 in http://www.math.rochester.edu/people/faculty/dangeba/geom-080399.pdf

12. May 9, 2009

### quasar987

I always had a sweet spot for the proof that $\sqrt{2}$ is irrational:

First observe that if an integer k is such that k² is even, then it means that k is even. To see this, prove the contrapositive: k odd ==> k² odd. Indeed, to say that f k is odd is equivalent to saying that k is of the form k=2n+1, and thus k²=4n²+4n+1=2(2n²+2n)+1. That is to say, k² is odd too.

Now, for the proof that $\sqrt{2}$ is irrational, let x be such that x²=2 and suppose x is rational: x=p/q with gcd(p,q)=1 (that is to say, p and q have no common divisor, that is to say, the fraction p/q is "reduced".) Squaring that equation yields p²=2q². That is to say, p² is even. So by the above lemma, p is even: p=2n. Thus q²=4n²/2=2n² and so q² and q are even too. But this is absurd because it means that gcd(p,q)$\geq$2 (that is to say, 2 is a common divisor of p and q, that is to say, the fraction p/q is not reduced.)! Thus x, and in particular, ±$\sqrt{2}$ are irrational.

13. May 9, 2009

### Russell Berty

Speaking of the square root of two… Here is a fun little nonconstructive existence proof.

Prove that there exists irrational numbers a and b such that a^b is rational.

Proof – Note that $$\sqrt{2}^{\sqrt{2}}$$

is either rational or irrational. We will argue by cases.

Case 1) If $$\sqrt{2}^{\sqrt{2}}$$
is rational then we have our irrational a and b, namely a=$$\sqrt{2}$$ and b=$$\sqrt{2}$$. Thus, in this case, there exists irrational numbers a and b such that a^b is rational.

Case 2) If $$\sqrt{2}^{\sqrt{2}}$$
is irrational then notice
$$\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{\sqrt{2}\sqrt{2}}=\sqrt{2}^{2}=2$$

Hence, letting a=$$\sqrt{2}^{\sqrt{2}}$$ and b=$$\sqrt{2}$$, we see in this case that there exists irrational numbers a and b such that a^b is rational.

In either case, there exists irrational a and b such that a^b is rational.

14. May 9, 2009

An ancient one but I like it Circle area=pi*r squared by dividing the circle into smaller and smaller slices.There's something fascinating about pi.

15. May 11, 2009

### Jamma

I saw this proof on the internet that 1=0, it was totally amazing.

16. May 11, 2009

### AUMathTutor

I like the proof that the halting problem is undecidable.