text:
Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals
Search results

Search: MSC category 11 ( Number theory )

 Expand all        Collapse all Results 51 - 75 of 243

51. CJM 2011 (vol 64 pp. 1201)

Aistleitner, Christoph; Elsholtz, Christian
 The Central Limit Theorem for Subsequences in Probabilistic Number Theory Let $(n_k)_{k \geq 1}$ be an increasing sequence of positive integers, and let $f(x)$ be a real function satisfying $$\tag{1} f(x+1)=f(x), \qquad \int_0^1 f(x) ~dx=0,\qquad \operatorname{Var_{[0,1]}} f \lt \infty.$$ If $\lim_{k \to \infty} \frac{n_{k+1}}{n_k} = \infty$ the distribution of $$\tag{2} \frac{\sum_{k=1}^N f(n_k x)}{\sqrt{N}}$$ converges to a Gaussian distribution. In the case $$1 \lt \liminf_{k \to \infty} \frac{n_{k+1}}{n_k}, \qquad \limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \lt \infty$$ there is a complex interplay between the analytic properties of the function $f$, the number-theoretic properties of $(n_k)_{k \geq 1}$, and the limit distribution of (2). In this paper we prove that any sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} = 1$ contains a nontrivial subsequence $(m_k)_{k \geq 1}$ such that for any function satisfying (1) the distribution of $$\frac{\sum_{k=1}^N f(m_k x)}{\sqrt{N}}$$ converges to a Gaussian distribution. This result is best possible: for any $\varepsilon\gt 0$ there exists a sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \leq 1 + \varepsilon$ such that for every nontrivial subsequence $(m_k)_{k \geq 1}$ of $(n_k)_{k \geq 1}$ the distribution of (2) does not converge to a Gaussian distribution for some $f$. Our result can be viewed as a Ramsey type result: a sufficiently dense increasing integer sequence contains a subsequence having a certain requested number-theoretic property. Keywords:central limit theorem, lacunary sequences, linear Diophantine equations, Ramsey type theoremCategories:60F05, 42A55, 11D04, 05C55, 11K06

52. CJM 2011 (vol 64 pp. 1248)

Gärtner, Jérôme
 Darmon's Points and Quaternionic Shimura Varieties In this paper, we generalize a conjecture due to Darmon and Logan in an adelic setting. We study the relation between our construction and Kudla's works on cycles on orthogonal Shimura varieties. This relation allows us to conjecture a Gross-Kohnen-Zagier theorem for Darmon's points. Keywords:elliptic curves, Stark-Heegner points, quaternionic Shimura varietiesCategories:11G05, 14G35, 11F67, 11G40

53. CJM 2011 (vol 64 pp. 588)

Nekovář, Jan
 Level Raising and Anticyclotomic Selmer Groups for Hilbert Modular Forms of Weight Two In this article we refine the method of Bertolini and Darmon and prove several finiteness results for anticyclotomic Selmer groups of Hilbert modular forms of parallel weight two. Keywords:Hilbert modular forms, Selmer groups, Shimura curvesCategories:11G40, 11F41, 11G18

54. CJM 2011 (vol 64 pp. 935)

McIntosh, Richard J.
 The H and K Families of Mock Theta Functions In his last letter to Hardy, Ramanujan defined 17 functions $F(q)$, $|q|\lt 1$, which he called mock $\theta$-functions. He observed that as $q$ radially approaches any root of unity $\zeta$ at which $F(q)$ has an exponential singularity, there is a $\theta$-function $T_\zeta(q)$ with $F(q)-T_\zeta(q)=O(1)$. Since then, other functions have been found that possess this property. These functions are related to a function $H(x,q)$, where $x$ is usually $q^r$ or $e^{2\pi i r}$ for some rational number $r$. For this reason we refer to $H$ as a universal'' mock $\theta$-function. Modular transformations of $H$ give rise to the functions $K$, $K_1$, $K_2$. The functions $K$ and $K_1$ appear in Ramanujan's lost notebook. We prove various linear relations between these functions using Appell-Lerch sums (also called generalized Lambert series). Some relations (mock theta conjectures'') involving mock $\theta$-functions of even order and $H$ are listed. Keywords:mock theta function, $q$-series, Appell-Lerch sum, generalized Lambert seriesCategories:11B65, 33D15

55. CJM 2011 (vol 64 pp. 1122)

Seveso, Marco Adamo
 $p$-adic $L$-functions and the Rationality of Darmon Cycles Darmon cycles are a higher weight analogue of Stark--Heegner points. They yield local cohomology classes in the Deligne representation associated with a cuspidal form on $\Gamma _{0}( N)$ of even weight $k_{0}\geq 2$. They are conjectured to be the restriction of global cohomology classes in the Bloch--Kato Selmer group defined over narrow ring class fields attached to a real quadratic field. We show that suitable linear combinations of them obtained by genus characters satisfy these conjectures. We also prove $p$-adic Gross--Zagier type formulas, relating the derivatives of $p$-adic $L$-functions of the weight variable attached to imaginary (resp. real) quadratic fields to Heegner cycles (resp. Darmon cycles). Finally we express the second derivative of the Mazur--Kitagawa $p$-adic $L$-function of the weight variable in terms of a global cycle defined over a quadratic extension of $\mathbb{Q}$. Categories:11F67, 14G05

56. CJM 2011 (vol 64 pp. 282)

Dahmen, Sander R.; Yazdani, Soroosh
 Level Lowering Modulo Prime Powers and Twisted Fermat Equations We discuss a clean level lowering theorem modulo prime powers for weight $2$ cusp forms. Furthermore, we illustrate how this can be used to completely solve certain twisted Fermat equations $ax^n+by^n+cz^n=0$. Keywords:modular forms, level lowering, Diophantine equationsCategories:11D41, 11F33, 11F11, 11F80, 11G05

57. CJM 2011 (vol 64 pp. 301)

Hurlburt, Chris; Thunder, Jeffrey Lin
 Hermite's Constant for Function Fields We formulate an analog of Hermite's constant for function fields over a finite field and state a conjectural value for this analog. We prove our conjecture in many cases, and prove slightly weaker results in all other cases. Category:11G50

58. CJM 2011 (vol 64 pp. 345)

McKee, James; Smyth, Chris
 Salem Numbers and Pisot Numbers via Interlacing We present a general construction of Salem numbers via rational functions whose zeros and poles mostly lie on the unit circle and satisfy an interlacing condition. This extends and unifies earlier work. We then consider the obvious'' limit points of the set of Salem numbers produced by our theorems and show that these are all Pisot numbers, in support of a conjecture of Boyd. We then show that all Pisot numbers arise in this way. Combining this with a theorem of Boyd, we produce all Salem numbers via an interlacing construction. Keywords:Salem numbers, Pisot numbersCategory:11R06

59. CJM 2011 (vol 64 pp. 81)

David, C.; Wu, J.
 Pseudoprime Reductions of Elliptic Curves Let $E$ be an elliptic curve over $\mathbb Q$ without complex multiplication, and for each prime $p$ of good reduction, let $n_E(p) = | E(\mathbb F_p) |$. For any integer $b$, we consider elliptic pseudoprimes to the base $b$. More precisely, let $Q_{E,b}(x)$ be the number of primes $p \leq x$ such that $b^{n_E(p)} \equiv b\,({\rm mod}\,n_E(p))$, and let $\pi_{E, b}^{\operatorname{pseu}}(x)$ be the number of compositive $n_E(p)$ such that $b^{n_E(p)} \equiv b\,({\rm mod}\,n_E(p))$ (also called elliptic curve pseudoprimes). Motivated by cryptography applications, we address the problem of finding upper bounds for $Q_{E,b}(x)$ and $\pi_{E, b}^{\operatorname{pseu}}(x)$, generalising some of the literature for the classical pseudoprimes to this new setting. Keywords:Rosser-Iwaniec sieve, group order of elliptic curves over finite fields, pseudoprimes Categories:11N36, 14H52

60. CJM 2011 (vol 64 pp. 151)

Miller, Steven J.; Wong, Siman
 Moments of the Rank of Elliptic Curves Fix an elliptic curve $E/\mathbb{Q}$ and assume the Riemann Hypothesis for the $L$-function $L(E_D, s)$ for every quadratic twist $E_D$ of $E$ by $D\in\mathbb{Z}$. We combine Weil's explicit formula with techniques of Heath-Brown to derive an asymptotic upper bound for the weighted moments of the analytic rank of $E_D$. We derive from this an upper bound for the density of low-lying zeros of $L(E_D, s)$ that is compatible with the random matrix models of Katz and Sarnak. We also show that for any unbounded increasing function $f$ on $\mathbb{R}$, the analytic rank and (assuming in addition the Birch and Swinnerton-Dyer conjecture) the number of integral points of $E_D$ are less than $f(D)$ for almost all $D$. Keywords:elliptic curve, explicit formula, integral point, low-lying zeros, quadratic twist, rankCategories:11G05, 11G40

61. CJM 2011 (vol 63 pp. 1328)

Gun, Sanoli; Murty, M. Ram; Rath, Purusottam
 On a Conjecture of Chowla and Milnor In this paper, we investigate a conjecture due to S. and P. Chowla and its generalization by Milnor. These are related to the delicate question of non-vanishing of $L$-functions associated to periodic functions at integers greater than $1$. We report on some progress in relation to these conjectures. In a different vein, we link them to a conjecture of Zagier on multiple zeta values and also to linear independence of polylogarithms. Categories:11F20, 11F11

62. CJM 2011 (vol 63 pp. 992)

Bruin, Nils; Doerksen, Kevin
 The Arithmetic of Genus Two Curves with (4,4)-Split Jacobians In this paper we study genus $2$ curves whose Jacobians admit a polarized $(4,4)$-isogeny to a product of elliptic curves. We consider base fields of characteristic different from $2$ and $3$, which we do not assume to be algebraically closed. We obtain a full classification of all principally polarized abelian surfaces that can arise from gluing two elliptic curves along their $4$-torsion, and we derive the relation their absolute invariants satisfy. As an intermediate step, we give a general description of Richelot isogenies between Jacobians of genus $2$ curves, where previously only Richelot isogenies with kernels that are pointwise defined over the base field were considered. Our main tool is a Galois theoretic characterization of genus $2$ curves admitting multiple Richelot isogenies. Keywords:Genus 2 curves, isogenies, split Jacobians, elliptic curvesCategories:11G30, 14H40

63. CJM 2011 (vol 63 pp. 1284)

Dewar, Michael
 Non-Existence of Ramanujan Congruences in Modular Forms of Level Four Ramanujan famously found congruences like $p(5n+4)\equiv 0 \operatorname{mod} 5$ for the partition function. We provide a method to find all simple congruences of this type in the coefficients of the inverse of a modular form on $\Gamma_{1}(4)$ that is non-vanishing on the upper half plane. This is applied to answer open questions about the (non)-existence of congruences in the generating functions for overpartitions, crank differences, and 2-colored $F$-partitions. Keywords:modular form, Ramanujan congruence, generalized Frobenius partition, overpartition, crankCategories:11F33, 11P83

64. CJM 2011 (vol 63 pp. 826)

Errthum, Eric
 Singular Moduli of Shimura Curves The $j$-function acts as a parametrization of the classical modular curve. Its values at complex multiplication (CM) points are called singular moduli and are algebraic integers. A Shimura curve is a generalization of the modular curve and, if the Shimura curve has genus~$0$, a rational parameterizing function exists and when evaluated at a CM point is again algebraic over~$\mathbf{Q}$. This paper shows that the coordinate maps given by N.~Elkies for the Shimura curves associated to the quaternion algebras with discriminants $6$ and $10$ are Borcherds lifts of vector-valued modular forms. This property is then used to explicitly compute the rational norms of singular moduli on these curves. This method not only verifies conjectural values for the rational CM points, but also provides a way of algebraically calculating the norms of CM points with arbitrarily large negative discriminant. Categories:11G18, 11F12

65. CJM 2011 (vol 63 pp. 1083)

Kaletha, Tasho
 Decomposition of Splitting Invariants in Split Real Groups For a maximal torus in a quasi-split semi-simple simply-connected group over a local field of characteristic $0$, Langlands and Shelstad constructed a cohomological invariant called the splitting invariant, which is an important component of their endoscopic transfer factors. We study this invariant in the case of a split real group and prove a decomposition theorem which expresses this invariant for a general torus as a product of the corresponding invariants for simple tori. We also show how this reduction formula allows for the comparison of splitting invariants between different tori in the given real group. Keywords:endoscopy, real lie group, splitting invariant, transfer factorCategories:11F70, 22E47, 11S37, 11F72, 17B22

66. CJM 2011 (vol 63 pp. 1220)

Baake, Michael; Scharlau, Rudolf; Zeiner, Peter
 Similar Sublattices of Planar Lattices The similar sublattices of a planar lattice can be classified via its multiplier ring. The latter is the ring of rational integers in the generic case, and an order in an imaginary quadratic field otherwise. Several classes of examples are discussed, with special emphasis on concrete results. In particular, we derive Dirichlet series generating functions for the number of distinct similar sublattices of a given index, and relate them to zeta functions of orders in imaginary quadratic fields. Categories:11H06, 11R11, 52C05, 82D25

67. CJM 2011 (vol 63 pp. 1107)

Liu, Baiying
 Genericity of Representations of p-Adic $Sp_{2n}$ and Local Langlands Parameters Let $G$ be the $F$-rational points of the symplectic group $Sp_{2n}$, where $F$ is a non-Archimedean local field of characteristic $0$. Cogdell, Kim, Piatetski-Shapiro, and Shahidi constructed local Langlands functorial lifting from irreducible generic representations of $G$ to irreducible representations of $GL_{2n+1}(F)$. Jiang and Soudry constructed the descent map from irreducible supercuspidal representations of $GL_{2n+1}(F)$ to those of $G$, showing that the local Langlands functorial lifting from the irreducible supercuspidal generic representations is surjective. In this paper, based on above results, using the same descent method of studying $SO_{2n+1}$ as Jiang and Soudry, we will show the rest of local Langlands functorial lifting is also surjective, and for any local Langlands parameter $\phi \in \Phi(G)$, we construct a representation $\sigma$ such that $\phi$ and $\sigma$ have the same twisted local factors. As one application, we prove the $G$-case of a conjecture of Gross-Prasad and Rallis, that is, a local Langlands parameter $\phi \in \Phi(G)$ is generic, i.e., the representation attached to $\phi$ is generic, if and only if the adjoint $L$-function of $\phi$ is holomorphic at $s=1$. As another application, we prove for each Arthur parameter $\psi$, and the corresponding local Langlands parameter $\phi_{\psi}$, the representation attached to $\phi_{\psi}$ is generic if and only if $\phi_{\psi}$ is tempered. Keywords:generic representations, local Langlands parametersCategories:22E50, 11S37

68. CJM 2011 (vol 63 pp. 591)

Hanzer, Marcela; Muić, Goran
 Rank One Reducibility for Metaplectic Groups via Theta Correspondence We calculate reducibility for the representations of metaplectic groups induced from cuspidal representations of maximal parabolic subgroups via theta correspondence, in terms of the analogous representations of the odd orthogonal groups. We also describe the lifts of all relevant subquotients. Categories:22E50, 11F70

69. CJM 2011 (vol 63 pp. 616)

Lee, Edward
 A Modular Quintic Calabi-Yau Threefold of Level 55 In this note we search the parameter space of Horrocks-Mumford quintic threefolds and locate a Calabi-Yau threefold that is modular, in the sense that the $L$-function of its middle-dimensional cohomology is associated with a classical modular form of weight 4 and level 55. Keywords: Calabi-Yau threefold, non-rigid Calabi-Yau threefold, two-dimensional Galois representation, modular variety, Horrocks-Mumford vector bundleCategories:14J15, 11F23, 14J32, 11G40

70. CJM 2011 (vol 63 pp. 634)

Lü, Guangshi
 On Higher Moments of Fourier Coefficients of Holomorphic Cusp Forms Let $S_{k}(\Gamma)$ be the space of holomorphic cusp forms of even integral weight $k$ for the full modular group. Let $\lambda_f(n)$ and $\lambda_g(n)$ be the $n$-th normalized Fourier coefficients of two holomorphic Hecke eigencuspforms $f(z), g(z) \in S_{k}(\Gamma)$, respectively. In this paper we are able to show the following results about higher moments of Fourier coefficients of holomorphic cusp forms.\newline (i) For any $\varepsilon>0$, we have \begin{equation*} \sum_{n\leq x}\lambda_f^5(n) \ll_{f,\varepsilon}x^{\frac{15}{16}+\varepsilon} \quad\text{and}\quad\sum_{n\leq x}\lambda_f^7(n) \ll_{f,\varepsilon}x^{\frac{63}{64}+\varepsilon}. \end{equation*} (ii) If $\operatorname{sym}^3\pi_f \ncong \operatorname{sym}^3\pi_g$, then for any $\varepsilon>0$, we have \begin{equation*} \sum_{n \leq x}\lambda_f^3(n)\lambda_g^3(n)\ll_{f,\varepsilon}x^{\frac{31}{32}+\varepsilon}; \end{equation*} If $\operatorname{sym}^2\pi_f \ncong \operatorname{sym}^2\pi_g$, then for any $\varepsilon>0$, we have $\sum_{n \leq x}\lambda_f^4(n)\lambda_g^2(n)=cx\log x+c'x+O_{f,\varepsilon}\bigl(x^{\frac{31}{32}+\varepsilon}\bigr);$ If $\operatorname{sym}^2\pi_f \ncong \operatorname{sym}^2\pi_g$ and $\operatorname{sym}^4\pi_f \ncong \operatorname{sym}^4\pi_g$, then for any $\varepsilon>0$, we have $\sum_{n \leq x}\lambda_f^4(n)\lambda_g^4(n)=xP(\log x)+O_{f,\varepsilon}\bigl(x^{\frac{127}{128}+\varepsilon}\bigr),$ where $P(x)$ is a polynomial of degree $3$. Keywords: Fourier coefficients of cusp forms, symmetric power $L$-functionCategories:11F30, , , , 11F11, 11F66

71. CJM 2011 (vol 63 pp. 481)

Baragar, Arthur
 The Ample Cone for a K3 Surface In this paper, we give several pictorial fractal representations of the ample or KÃ¤hler cone for surfaces in a certain class of $K3$ surfaces. The class includes surfaces described by smooth $(2,2,2)$ forms in ${\mathbb P^1\times\mathbb P^1\times \mathbb P^1}$ defined over a sufficiently large number field $K$ that have a line parallel to one of the axes and have Picard number four. We relate the Hausdorff dimension of this fractal to the asymptotic growth of orbits of curves under the action of the surface's group of automorphisms. We experimentally estimate the Hausdorff dimension of the fractal to be $1.296 \pm .010$. Keywords:Fractal, Hausdorff dimension, K3 surface, Kleinian groups, dynamicsCategories:14J28, , , , 14J50, 11D41, 11D72, 11H56, 11G10, 37F35, 37D05

72. CJM 2011 (vol 63 pp. 298)

Gun, Sanoli; Murty, V. Kumar
 A Variant of Lehmer's Conjecture, II: The CM-case Let $f$ be a normalized Hecke eigenform with rational integer Fourier coefficients. It is an interesting question to know how often an integer $n$ has a factor common with the $n$-th Fourier coefficient of $f$. It has been shown in previous papers that this happens very often. In this paper, we give an asymptotic formula for the number of integers $n$ for which $(n, a(n)) = 1$, where $a(n)$ is the $n$-th Fourier coefficient of a normalized Hecke eigenform $f$ of weight $2$ with rational integer Fourier coefficients and having complex multiplication. Categories:11F11, 11F30

73. CJM 2010 (vol 63 pp. 277)

Ghate, Eknath; Vatsal, Vinayak
 Locally Indecomposable Galois Representations In a previous paper the authors showed that, under some technical conditions, the local Galois representations attached to the members of a non-CM family of ordinary cusp forms are indecomposable for all except possibly finitely many members of the family. In this paper we use deformation theoretic methods to give examples of non-CM families for which every classical member of weight at least two has a locally indecomposable Galois representation. Category:11F80

74. CJM 2010 (vol 63 pp. 241)

Essouabri, Driss; Matsumoto, Kohji; Tsumura, Hirofumi
 Multiple Zeta-Functions Associated with Linear Recurrence Sequences and the Vectorial Sum Formula We prove the holomorphic continuation of certain multi-variable multiple zeta-functions whose coefficients satisfy a suitable recurrence condition. In fact, we introduce more general vectorial zeta-functions and prove their holomorphic continuation. Moreover, we show a vectorial sum formula among those vectorial zeta-functions from which some generalizations of the classical sum formula can be deduced. Keywords:Zeta-functions, holomorphic continuation, recurrence sequences, Fibonacci numbers, sum formulasCategories:11M41, 40B05, 11B39

75. CJM 2010 (vol 63 pp. 136)

Gun, Sanoli; Murty, M. Ram; Rath, Purusottam
 Transcendental Nature of Special Values of $L$-Functions In this paper, we study the non-vanishing and transcendence of special values of a varying class of $L$-functions and their derivatives. This allows us to investigate the transcendence of Petersson norms of certain weight one modular forms. Categories:11J81, 11J86, 11J91
 Page Previous 1 2 3 4 ... 10 Next
 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2016 : https://cms.math.ca/


text:
# Identifying poisoned wines

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned one by feeding the wines to the rats. The poisoned wine takes exactly one hour to work and is undetectable before then. How many rats are necessary to find the poisoned bottle in one hour?

It is not hard to see that the answer is $10$. Way back when math.SE first started, a generalization was considered where more than one bottle of wine is poisoned. The strategy that works for the standard version fails for this version, and I could only find a solution for the case of $2$ poisoned bottles that requires $65$ rats. Asymptotically my solution requires $O(\log^2 N)$ rats to detect $2$ poisoned bottles out of $N$ bottles.

Can anyone do better asymptotically and/or prove that their answer is optimal and/or find a solution that works for more poisoned bottles? The number of poisoned bottles, I guess, should be kept constant while the total number of bottles is allowed to become large for asymptotic estimates.

-
From the viewpoint of a rat, any bottle of wine sounds like alcohol poisoning. – KConrad Mar 29 '11 at 4:26
I don't know how to do the problem, but I can't help feeling it's equivalent to finding a 2-error-correcting binary code of minimal dimension given ... something-or-other. I'm pretty sure the solution to the 1-bottle problem can be expressed in terms of the Hamming codes, and if you do that then maybe what I'm saying about 2-error-correcting codes will become clear. – Gerry Myerson Mar 29 '11 at 5:12
@Thomas: sure. After an hour, the only information you have if you used $m$ rats is the information about which rats are dead or alive, so you can only get $m$ bits of information this way. So $\lceil \log N \rceil$ is optimal for one bottle. – Qiaochu Yuan Mar 29 '11 at 5:47
@Roland You have only one hour to perform the test so you cannot wait to see which rats survive to reuse them. Otherwise, it would be easy: one would simply administrate the different wines successively to a single rat until it dies. – Anthony Leverrier Mar 29 '11 at 9:58
Isn't this what postdocs are for? – Mariano Suárez-Alvarez Jun 8 '11 at 4:23

Each bottle of wine corresponds to the set of rats who tasted it. Let $\mathcal{F}$ be the family of the resulting sets. If bottles corresponding to sets $A$ and $B$ are poisoned then $A \cup B$ is the set of dead rats. Therefore we can identify the poisoned bottles as long as for all $A,B,C,D \in \mathcal{F}$ such that $A \cup B = C \cup D$ we have $\{ A, B \} = \{ C, D \}$. Families with this property are called (strongly) union-free and the maximum possible size $f(n)$ of a union free family $\mathcal{F} \subset 2^{ [n] }$ has been studied in extremal combinatorics. In the question context, $f(n)$ is the maximum number of bottles of wine which can be tested by $n$ rats.

In the paper "Union-free Hypergraphs and Probability Theory" Frankl and Furedi show that $$2^{(n-3)/4} \leq f(n) \leq 2^{(n+1)/2}.$$ The proof of the lower bound is algebraic, constructive, and, I think, very elegant. In particular, one can find $2$ poisoned bottles out of $1000$ with $43$ rats.

-
+1: very nice, now the rats have no chance ;-) – Suvrit Apr 1 '11 at 21:49
Perhaps oddly, I find myself caring more about the abstract formulation than about the puzzle formulation. Will have to look at the FF paper when I find time! – Yemon Choi Apr 1 '11 at 23:03
Many thanks! This question has been bothering me for quite some time. – Qiaochu Yuan Apr 2 '11 at 1:56

This problem also goes by the name "nonadaptive combinatorial group testing" and has been around since at least World War II, when the U.S. government was trying to isolate syphilis cases in soldiers. ("Nonadaptive" means you have to specify all the tests in advance, whereas "adaptive" means you can use the results from previous tests before deciding which ones to do next.)

The standard reference on group testing appears to be Combinatorial Group Testing and Its Applications, by Du and Hwang. Part II, which comprises Chapters 7-9, is on nonadaptive testing. In particular, finding optimal testing structures when there are two or more "defectives" is still an open problem.

However, if $t(d,n)$ is the number of tests required to isolate $d$ defectives out of $n$ total subjects, the bounds $\Omega(\frac{d^2}{\log d} \log n) \leq t(d,n) \leq O(d^2 \log n)$ are known. The Wikipedia article on disjunct matrices has a discussion and some proofs.

It might be interesting to compare the solution for the adaptive version of this problem, as we can give a definite answer in this case.

Let $n(t)$ denote the maximum number of bottles of wine for which 2 poisoned ones can be identified in $t$ adaptive tests. In "Group testing with two and three defectives" (Annals of the New York Academy of Sciences 576, pp. 86-96, 1989) Chang, Hwang, and Weng give explicit testing procedures that yield the lower bounds $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text{ even, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ odd, } t \geq 13.$$

In the Du and Hwang text it is shown that, for $t \geq 4$, we have the upper bound $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$
(Note that this is the upper bound on $f(n)$ given in Sergey Norin's answer.)

These bounds tell us that $n(18) \leq 723$ but that $n(19) \geq 1008$. Thus 2 poisoned bottles can be identified out of 1000 in 19 adaptive tests but no fewer, using the testing procedure described in the Chang, Hwang, and Weng paper.

-

You yourself give the solution in the link: the probabilistic method. Without trying to optimize, take $r$ rats and for each one choose the subset of wines randomly, each wine with probability $1/2$ (say). Call these subsets $A_m$. Now let $\{i,j\}$ and $\{k,l\}$ be two possibilities for which bottles are poisoned. We want to know whether there's a rat separating these two possibilities, that is, that the outcome if the $i$-th and $j$-th bottles are the poisoned one will be different for that rat, then if the $k$-th and $l$-th bottles are poisoned. For any specific rat, this happens if $A_m$ intersects $\{i,j\}$ but not $\{k,l\}$ or vice verse. This happens with some fixed positive probability (again, not optimizing). Therefore, it fails with probability $q$ which is strictly less than 1. Hence, the probability for it to fail for all $\{A_m\}_{m=1}^r$ is $q^r$. There are less than $n^4$ pairs of possibilities for poisoned wine bottles, hence the probability of having some pair for which this fails is at most $n^4 q^r$ and taking $r=C \log n$ suffices to make this negligible.

-
I guess the problem is not to find a solution that works on average but one working in the worst case. – Anthony Leverrier Mar 29 '11 at 7:09
This works in the worst case. With high probability, if you have $r=1000 \log n$ rats and choose the subsets of wine bottles randomly each with probability $1/2$ you get a solution which work in the worst case (i.e. no matter which pair of bottles are poisoned). – Ori Gurel-Gurevich Mar 29 '11 at 7:16
I believe that since there are exponentially many choices for the probabilistic experiment, but only polynomially many ways the poison could be picked, there is some single string of random bits that works with $O(\log n)$ rats for all possible arrangements of the bottles. This requires using a concentration bound, such as Chernoff bounds. – Derrick Stolee Mar 29 '11 at 13:25
If I'm not mistaken, the optimal choice here is probability 1/3, leading to $r\sim\frac{3\log n}{\log(27/19)}$. For $n=1000$, this gives $r=59$. – Emil Jeřábek Mar 29 '11 at 13:27
@Zander: It's possible my argument is flawed, but I don't think so. The random variables $\{A_m\}_{m=1}^r$ are, by definition, independent, so the events are also independent. The events aren't independent for different $i,j,k,l$, but for that part I use union bound. (a general remark, I suggest using a less determined tone in your comments, such as "I think there is a flaw in the argument" or even "I don't understand this part, can you explain it", see the beginning of this comment. – Ori Gurel-Gurevich Mar 30 '11 at 5:19

There's a very similar problem in compressed sensing genetic screening for rare alleles (cf http://nar.oxfordjournals.org/content/38/19/e179.full ). The technique almost works here provided we can determine how much poison a rat gets. Seems reasonable, a rat that gets more poison dies faster.

In our problem the idea would be to create a sample for each rat to drink by randomly pooling together wine from many bottles. Specifically, for rat $i$ we draw $A_{ij}$ liters of wine from each of the $j=1,...,N$ bottles where $A_{ij}$ is $\mathcal{N}(0,1)$ distributed. Let $b_i$ denote the amount of poison measured in rat $i$ and let $x_j$ denote the amount of poison in bottle $j$.

This yields the highly underdetermined linear system $$A\vec{x} = \vec{b}$$ where we know a priori that $\vec{x}$ is sparse. The sparsest solution to this linear system may obtained in polynomial time by solving the convex optimization $$\min |\vec{x}|_1 \text{ s.t. } A\vec{x}=\vec{b}$$

The number of rats required here is $\mathcal{O}(s \log(N))$ where $s$ is the number of poison bottles.

-

For the case of one poisoned bottle I would expect the answer to be logbase2(N) because we could then have each rat drink from the bottles whose positions' binary digits include the rat's position and the rats that die will be those whose positions give the binary representation of the bad bottle's position.

If that is correct then for two bad bottles I would be inclined to think of doing the same thing with the list of all bottle pairs, but of course there is not just one poisonous pair. In order to identify the unique doubly poisonous pair we need to replace the rats by something that only dies if it gets a double dose. It seems that pairs of rats would suffice for this, but then the total number needed would be 2*logbase2(NC2) which gives only 38 for N=1000, so if your answer is optimal I must have missed something.

Where did I go wrong?

-
Try it for something smaller, like $N=5$, where you can write everything out, and see if your proposed protocol (which you haven't actually given) works. – Gerry Myerson Mar 29 '11 at 6:15
It is not known (by me) that Qiaochu's answer is optimal. Also, an obvious use of pairs of rats only pins down those digits in the encoding that the two bottles share. You need a parallel encoding and additional rats to determine which two bottles are affected, within an hour. I suspect, using three randomly chosen encodings and 60 rats, one has a high probability of success of identifying the two bottles. Now if I only had a proof... . Gerhard "Off To See The Wizard" Paseman, 2011.03.28 – Gerhard Paseman Mar 29 '11 at 6:35
Yes, of course you are right. A pair of rats could die from two single doses, each from a bottle-pair with only one bad bottle. – Alan Cooper Mar 29 '11 at 8:10

format: plain


text:
## College Algebra 7th Edition

multiply $3^{8}$
When we raise a power to new power , we multiply the exponents. So, $(3^{4})^{2}$ = $3^{4\times2}$ = $3^{8}$


text:
## drumjockey83 Find the average of the function over the interval (0,2) f(x)=4e^(-6x) one year ago one year ago

1. y2o2

$\large{ {f(0) + f(2)} \over { 2 - 0}}$

2. drumjockey83

yes but how would that play into the function

3. y2o2

$\huge = {2 \over e^{12}}+2$

4. drumjockey83


text:
dc.contributor.author Aharonian, F. en_US dc.contributor.author Büsching, I. en_US dc.contributor.author Davids, I.D. en_US dc.contributor.author De Jager, O.C. en_US dc.contributor.author Holleran, M. en_US dc.contributor.author Raubenheimer, B.C. en_US dc.contributor.author Venter, C. dc.date.accessioned 2010-08-04T15:37:46Z dc.date.available 2010-08-04T15:37:46Z dc.date.issued 2009 en_US dc.identifier.citation Aharonian, F. et al. 2009. Spectrum and variability of the Galactic center VHE y-ray source HESS J1745-290. Astronomy and astrophysics, 503(3):817-825. [https://doi.org/10.1051/0004-6361/200811569 ] en_US dc.identifier.issn 0004-6361 dc.identifier.issn 1432-0746 (Online) dc.identifier.uri http://hdl.handle.net/10394/3541 dc.identifier.uri https://doi.org/10.1051/0004-6361/200811569 dc.description.abstract Aims. A detailed study of the spectrum and variability of the source HESS J1745-290 in the Galactic Center (GC) region using new data from the H.E.S.S. array of Cherenkov telescopes is presented. Flaring activity and quasi periodic oscillations (QPO) of HESS J1745-290 are investigated. Methods. The image analysis is performed with a combination of a semi-analytical shower model and the statistical moment-based Hillas technique. The spectrum and lightcurves of HESS J1745-290 are derived with a likelihood method based on a spectral shape hypothesis. Rayleigh tests and Fourier analysis of the H.E.S.S. GC signal are used to study the periodicity of the source. Results. With a three-fold increase in statistics compared to previous work, a deviation from a simple power law spectrum is detected for the first time. The measured energy spectrum over the three years 2004, 2005 and 2006 of data taking is compatible with both a power law spectrum with an exponential cut-off and a broken power law spectrum. The curvature of the energy spectrum is likely to be intrinsic to the photon source, as opposed to effects of interstellar absorption. The power law spectrum with an exponential cut-off is characterized by a photon index of 2.10 $\pm$ 0.04 $_{{\rm stat}}$ $\pm$ 0.10 $_{{\rm syst}}$ and a cut-off energy at 15.7 $\pm$ 3.4 $_{{\rm stat}}$ $\pm$ 2.5 $_{{\rm syst}}$ TeV. The broken power law spectrum exhibits spectral indices of 2.02 $\pm$ 0.08 $_{{\rm stat}}$ $\pm$ 0.10 $_{{\rm syst}}$ and 2.63 $\pm$ 0.14 $_{{\rm stat}}$ $\pm$ 0.10 $_{{\rm syst}}$ with a break energy at 2.57 $\pm$ 0.19 $_{{\rm stat}}$ $\pm$ 0.44 $_{{\rm syst}}$ TeV. No significant flux variation is found. Increases in the $\gamma$-ray flux of HESS J1745-290 by at least a factor of two would be required for a 3$\sigma$ detection of a flare with time scales of an hour. Investigation of possible QPO activity at periods claimed to be detected in X-rays does not show any periodicities in the H.E.S.S. signal dc.description.uri http://www.aanda.org/index.php?option=com_article&access=standard&Itemid=129&url=/articles/aa/full_html/2009/33/aa11569-08/aa11569-08.html dc.publisher EDP Sciences dc.subject Galaxy: center dc.subject Gamma rays: observations dc.subject Methods: data analysis dc.title Spectrum and variability of the Galactic center VHE y-ray source HESS J1745-290 en_US dc.contributor.researchID 12006653 - Venter, Christo dc.contributor.researchID 10179240 - Raubenheimer, Barend Christoffel dc.contributor.researchID 10859748 - Holleran, Mathew dc.contributor.researchID 10065857 - De Jager, Ocker Cornelis dc.contributor.researchID 13146629 - Davids, Isak Delberth dc.contributor.researchID 13235176 - Büsching, Ingo

Theme by


text:
Bitwise sum

Revision en1, by TheMartian0x48, 2021-06-14 08:38:41

You are given an integer K.
A function F is defined over non-negative integers as the following:

$F(x) = \sum((x | i) - (x \& i))$

for i such that the given conditions hold true:

$0 <= i <= x \text{ and } ((x | i) - (x \& i)) = x - i$

Determine the number of non-negative integers x such that

$F(x) \leq K$

| = bitwise or
& = bitwise and

Example for K = 6, possible x is 0, 1, 2, 3 and 4 as F(0) = 0
F(1) = 1
F(2) = 2
F(3) = 6
F(4) = 4

Constraints

$1 \leq T \leq 10^{5} \\ 1 \leq K \leq 10^{18} \\ \text{Time Limit: 5.0 sec(s) for each input file.} \\ \text{Memory Limit: 256 MB}$

It was asked in nokia coding hackthon.
I wasn't able to find any pattern to approach any optimal solution. How would you approach this problem?

History

Revisions

Rev. Lang. By When Δ Comment
en1 TheMartian0x48 2021-06-14 08:38:41 856 Initial revision (published)


text:
Numerical Methods: Integration of given function using Simpson’s 3/8 rule in C

Source Code:

SHARE Numerical Methods: Integration of given function using Simpson’s 3/8 rule in C


text:
Mikey asked in Science & MathematicsPhysics · 1 month ago

# motion in 1 dimension question ?

This is the x-t graph of

the motion of a

particle. Of the four

points P, Q, R, and S,

the acceleration a is greatest (most positive)

at

Relevance
• Amy
Lv 7
1 month ago

Acceleration is the second derivative of position (x).

Estimate how the velocity (slope) is changing at each of the points. E.g. it's changing slowly at point P, which means acceleration is close to zero.

• 1 month ago

velocity is the slope of the curve, the first derivative. Acceleration is the slope of the slope, the second derivative. The latter is difficult to see....

but the velocity starts at zero, increases to P then decreases until Q where the velocity is zero. It then increases in the negative direction, maximizing at P and goes back to zero at S.

Given that, I would have to guess at P being where the acceleration is max positive... if I had to pick one of those points... but I'd pick somewhere between R and S as the actual max. See below. Acc is slope of the red curve...


text:
# Factor3

less info
reputation
9
bio website location United States age 35 member for 2 years, 2 months seen Nov 27 at 4:09 profile views 36

# 40 Actions

 Nov28 awarded Popular Question Nov19 comment Mathjax expression in sphinx python not rendering correclty @mzjn, thanks. So to clarify, the function :math:'\sigma_t \triangleq X + Y' would likely not render inside a Python docstring, and should be written as :math:r'\sigma_t \triangleq X + Y', and will render in a Python docstring properly? Nov15 comment Mathjax expression in sphinx python not rendering correclty I think it would be helpful to show the original equation: w_k^* = \min_{w_k} \ell_k(w_k) + \lambda\left(\alpha||w_k||_1 + \frac{1}{2}(1-\alpha) ||w_k||^2\right), and then show how it needs to be altered in order to have autodoc read it correctly inside of a Python docstring. Nov6 comment What are simple instructions for creating a Python package structure and egg? ....years later... The user was a beginner and looking for a "step by step guide" to packaging, and the Hitchiker's Guide to Packaging is just that, great job of providing exactly what was asked for. Aug18 awarded Popular Question Aug6 comment Simpler way to put PDB breakpoints in Python code? to clarify this point, if I pdb.set_trace() and go into the debugger, use the l command (list) and see that I want to set a breakpoint at line 27, I would then enter: b 27 and the debugger would set a breakpoint at line 27 (I found the documentation a little challenging to understand, so wanted to add that point of clarification). Mar23 comment sheets of Excel Workbook from a URL into a pandas.DataFrame Perfect, thanks so much for the clear and prompt reply. Mar23 accepted sheets of Excel Workbook from a URL into a pandas.DataFrame Mar23 asked sheets of Excel Workbook from a URL into a pandas.DataFrame Jan10 awarded Popular Question Dec28 comment How to: reduce number of ticks with matplotlib This was a great suggestion, also being able to specify pyplot.locator_params(axis = 'x', nbins = 4) (or axis = 'y') made the process really straightforward. Thanks @bgamari! Dec28 answered adjusting heights of individual subplots in matplotlib in Python Nov13 awarded Commentator Nov13 accepted pandas.DataFrame.apply in a row by row operation Nov13 comment pandas.DataFrame.apply in a row by row operation Thanks @Wes, that last part In[23]: was exactly what I was looking for. Nov7 comment pandas.DataFrame.apply in a row by row operation Thanks @Aman, that gets the end result (as does df.values.sort(axis = 1), but doesn't it seem like df.sort(axis = 1) should accomplish the same thing? Also, I'm looking for an implementation in the form DataFrame.apply(func, axis = 1) for other row-wise functionality I'm building. Nov7 revised pandas.DataFrame.apply in a row by row operation added 102 characters in body Nov7 asked pandas.DataFrame.apply in a row by row operation May24 answered numpy: frequency counts for unique values in an array Mar7 comment Simple cross-tabulation in pandas So are you saying that each .csv file is just a single row, and then in that single row the first value is the year followed by the data as you present it above?


text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# Prospects for strongly coupled atom-photon quantum nodes

## Abstract

We discuss the trapping of cold atoms within microscopic voids drilled perpendicularly through the axis of an optical waveguide. The dimensions of the voids considered are between 1 and 40 optical wavelengths. By simulating light transmission across the voids, we find that appropriate shaping of the voids can substantially reduce the associated loss of optical power. Our results demonstrate that the formation of an optical cavity around such a void could produce strong coupling between the atoms and the guided light. By bringing multiple atoms into a single void and exploiting collective enhancement, cooperativities ~400 or more should be achievable. The simulations are carried out using a finite difference time domain method. Methods for the production of such a void and the trapping of cold atoms within it are also discussed.

## Introduction

The introduction of cold atoms into microscopic holes in optical waveguides allows the integration of atomic components into otherwise purely photonic devices, with potential applications in sensing and quantum information processing1,2. While alternative techniques are available for coupling guided light to cold atoms — for example the use of tapered nanofibres3,4,5 or hollow core fibres6,7,8 — microscopic holes offer a unique set of advantages that make them ideally suited for certain applications. Firstly, the technique of introducing cold atoms via a microscopic hole is just as applicable in a 2D waveguide chip as in a fibre, allowing the direct combination of cold atoms with photonic circuit devices. Secondly, while the overall optical depth of an atom cloud contained in a microscopic hole is likely to be less than that obtained using a nanofibre or hollow core fibre, the optical depth per unit length should be able to match that achievable in free space, which is substantially greater than that typical of hollow core fibre or nanofibre experiments. This may have important implications for spatial resolution in sensing applications. Finally, the spatial separation between the atoms and the solid material of the waveguide can be much larger in a microscopic hole than is typical of a hollow core fibre or possible using a nanofibre. This will be important in precision sensing and spectroscopy experiments, where atom-surface interactions might otherwise adversely affect the results, as well as for any experiments involving Rydberg atoms, which are currently one of the most promising candidates for the implementation of multi-qubit gates9,10,11.

In this article we simulate transmission of light across microscopic holes in optical waveguides. We focus on holes drilled perpendicular to the core of the waveguide, with diameters in the range of 1 to 40 optical wavelengths. Holes of this kind can be fabricated by pulsed laser drilling12,13 — see for example those shown in Fig. 1(d), which were fabricated by Workshop of Photonics14 in 2015. We find that appropriate shaping of the holes can significantly improve the overlap of the transmitted light with the guided mode, thus reducing the losses associated with traversing the hole, and present results for a range of different shapes of hole. We then discuss the implications of our results with respect to the prospects of reaching the strong coupling regime for atoms confined in such a hole. We also examine the intensity distribution of the light inside the hole and use our results to show that both crossed and individual waveguides are capable of forming a full, 3D dipole trap for ultracold atoms using only guided light.

While this article focuses on the specific application of a light-atom interface, the results may also be applicable within other fields. These include fibre-based gas sensors15,16 and the efficient transmission of light through integrated optical or optofluidic elements17,18 in a fibre or waveguide chip. Coupling of light between waveguides and/or optical fibres is also an important area of application.

## Simulation Methods

In order to identify a geometry which allows a gap in the micrometer range with high optical transmission, simulations based on solving Maxwell’s equations were performed using Optiwave software (Optiwave Systems Inc.). For most data we use a three dimensional finite difference time domain (FDTD) method, which is a numerical solution of the full Maxwell’s equations19.

Where applicable, we compare that to the results of a beam propagation method (BPM). While numerically less intensive than the FDTD method, the BPM we employ makes several approximations — most notably the paraxial approximation — that render it less accurate than the FDTD method. We therefore use it only as a guide to the overall trends in the system’s behaviour, which helps to highlight the most interesting areas for investigation with the more time-consuming FDTD simulations.

The key parameters of the FDTD simulation method are the mesh spacing in each dimension Δx, Δy, Δz (with the z axis corresponding to the direction of light propagation along the waveguide), the time step size Δt and the number of time steps for which the simulation was run, Nt. The parameters used for each simulation are given in Supplementary Table 1. The finite size of the spatial and temporal discretisation inevitably leads to a numerical error in the results of the simulations, an estimate of which is shown as error bars. Full details of how we estimate the magnitude of this error are given in the supplementary material. The boundary condition used for the FDTD simulations was the built-in anisotropic, perfectly-matched layers (PML) condition, which accurately approximates a perfect absorber.

In general we consider the overlap of the transmitted light with the fundamental mode of the waveguide (MOTL), rather than the transmission coefficient. The difference between these two is the additional loss of light resulting from reflections at the glass to air/vacuum interfaces. In the case of rectangular holes interference effects are important, and the reflection coefficient varies strongly with the length of the hole. We therefore calculated reflection coefficients for several illustrative cases of rectangular hole. The maximum and minimum (excluding sub-wavelength holes where the reflection coefficient tends to zero as the length tends to zero) were 17.8% and 0.5%, occurring for holes with lengths of 4 and 1.7 micrometers respectively. Reflection coefficients for rectangular holes with lengths of 1, 5, 12, 22 and 30 micrometers were found to be 15.9, 1.6, 14.8, 15.6 and 11.9% respectively.

It is also worth noting that for rectangular holes the reflected light typically overlaps well (~97% intensity overlap) with the guided mode of the waveguide. Therefore, if such a hole were placed inside an optical resonator, it would not be accurate to regard the majority of the reflected light as lost from the system.

However, calculation of accurate reflection/transmission coefficients requires a long simulation time, to allow for multiple reflections within the system. When the surfaces of the hole have even modest curvature, the poor overlap and phase averaging between the light reflected via different pathways means that interference effects are essentially negligible, and the reflection losses at each interface can be treated as independent. This yields reflection losses of ~4% per interface, with little variation according to the parameters of the hole. In these cases the MOTL is therefore the most interesting system property to consider.

With a specific application in mind, i.e. the interaction of photons with Caesium atoms, we consider the case of 852 nm light (resonant with the D2 line in Caesium) in a waveguide whose refractive index profile matches a commercial optical fibre (Thorlabs 780 HP), as a representative example for a typical singlemode optical waveguide. However, the general trends and qualitative behaviours observed are likely to be widely applicable. We also consider a specific case based on the waveguide chip described in1, for which we find agreement between our simulations and the work of the original authors.

## Simulation Results

The first hole shape considered is the simplest geometry — a cylinder, and the results are plotted in Fig. 2(a). The dip in MOTL between 10 and 1.5 μm is due to additional divergence caused by the concave surface curvature, and MOTL eventually tends upwards to 1 as the hole size is reduced to zero. For holes with diameters greater than about three micrometers, the highest achievable MOTL is ~39%. This occurs at a plateau of MOTL as a function of diameter, for hole diameters from 20 to 40 micrometers.

The next case considered was a rectangular hole, as the flat faces of the rectangular hole were expected to eliminate the dip at small radii seen in the cylindrical hole due to concave lensing effects. This was indeed found to be the case, and the results are plotted in Fig. 2(b).

The FDTD and BPM results show a similar trend, where the FDTD result is consistently lower, owing to the remaining inaccuracy of the BPM data due to the paraxial approximation not covering all beam paths in this regime. For holes up to 10 optical wavelengths, a mode overlap >95% is achievable.

For rectangular holes some experimental data is available in the literature1. This was found to yield 65% power transmission across a 16 μm gap between 4 μm square waveguides in silica. Based on the refractive index contrast (0.75%) and laser wavelength used, we simulated this situation using the FDTD method and found an estimated transmission of ~78% (including reflection losses). The theoretical result is an upper bound to what is achievable experimentally and the slightly lower result can be explained by potential imperfections in the polishing of the end facets, a small angle between the end facets or a small amount of contamination. We therefore find that these figures are consistent with our expectations.

From the two initial simulations, it was expected that the use of convex surfaces should enhance the mode overlap for larger holes, as the focal power of these surfaces will compensate for the beam divergence related to the numerical aperture of the fibre core and allow recapture of light into the guided mode.

One relevant case to consider is that of a hole with spherically-curved surfaces on the input and output facets. We simulated this case for a range of radii of curvature, with the closest approach between the input and output surfaces being locked to 30 μm. The results are plotted in Fig. 3(a). It can be seen from the FDTD simulations that for a radius of curvature of ~16 μm the MOTL exceeds 93%, a major improvement over the rectangular hole of 30 μm length where the MOTL was only ~70% (see Fig. 2(b)). As a consistency check, additional simulations were also run for radii of curvature up to 3 mm, well beyond the range of Fig. 3(a). It was confirmed that, as expected, the MOTL gradually drops off as the radius of curvature is increased and ultimately tends to the same value predicted for the 30 μm rectangular hole.

With the practicalities of making a hole of this shape in mind, we also considered the effect of using cylindrically curved convex surfaces instead of spherically curved surfaces. We expect such holes to be easier to make as they have a constant cross-section. The results are shown in Fig. 3(b).

Parabolic surface curvatures were also investigated using the FDTD method, and were found to provide even better mode overlap for the transmitted light. The results are plotted in Fig. 4(a). In particular, for circularly symmetric, convex, parabolic surface curvature of the hole surfaces with $$\alpha =\frac{\delta z}{{r}^{2}}=0.068\,\mu {{\rm{m}}}^{-1}$$ we find $${\mathrm{(99.5}}_{-1.3}^{+0.5}) \%$$ MOTL for a hole where the distance of closest approach is 20 μm. The convex surfaces also lead to focusing of the light within the hole. The enhancement in peak intensity that results from this could be useful for the production of an optical dipole trap within the hole (see below), or to allow the strong coupling regime to be reached with smaller atomic ensembles as discussed below. We observe enhancements of up to a factor of 15.5 in peak intensity, with a general trend towards greater surface curvature producing a larger peak intensity enhancement. In the example given above (parabolic curvature with α = 0.068 μm−1) we find that the peak intensity is increased by a factor of ~5.

In order to constitute a quantum memory, or to allow longer interrogation times in sensing applications, it is advantageous to hold cold atoms within the junction, e.g. in an optical dipole trap. Where in other systems the creation of a small stable trap could be challenging, here they can be created using only light guided in the waveguides themselves. The trapping region then also automatically overlaps with the interrogation region of the probe light.

The FDTD method of simulation provides full data on the electric field as a function of position within the junction and can therefore be used to determine the light intensity, and hence the optical dipole potential, as a function of position within the junction. Figure 5(a) shows the dipole potential generated for Cs atoms by 1 mW of light at 1064 nm crossing a 20 μm hole with convex parabolic surface curvature (α = 0.063 μm−1) in a waveguide with parameters matching Thorlabs 780 HP optical fibre. It can be seen from this that already a single beam forms a full 3D trap - a result of focusing of the guided light at the convex interfaces. Figure 5(b) shows the dipole potential generated in a junction formed at the intersection of two 4 μm square silica waveguides with a refractive index contrast of 0.75%. There is assumed to be 1 mW of 1064 nm light in each waveguide, with identical linear polarisations. It is worth noting that the small mode area offers an unusually high trap depth for a given optical power and wavelength.

The damage threshold for waveguides and optical fibres of this type is typically of the order of 1010 Wm−2 for visible and NIR wavelengths. This would correspond to a power of ~200 mW in each waveguide. As a result, the maximum trap depth that can realistically be achieved in such a junction (with a comparable detuning of the trapping laser from the relevant atomic transition) would be on the order of 10 to 15 mK.

## Strong Coupling Regime

Reaching the strong coupling regime is of interest as it permits single-photon gate operations and allows the observation and exploitation of quantum electrodynamic effects20,21,22,23,24. In order to reach this regime an optical cavity would be produced around a quantum system with an appropriate optically-addressable transition, in this case via the use of laser-written Bragg gratings20,25 on either side of the hole. Different regimes can then be reached, depending on the cavity length and the choice of hole type. The strong coupling regime is defined as the regime in which the atom-cavity coupling constant g1 significantly exceeds the atomic decay rate γ and the cavity decay rate κ. The Purcell regime, in which the cooperativity $$C={g}_{1}^{2}/(\kappa \gamma )$$ is large but g1 < κ, is also of interest — particularly with regard to the production of single photon sources26. For completeness, note that there are a few alternative definitions of C in the literature. The maximum value of the atom-cavity coupling constant is given according to2

$${g}_{1}=\zeta \sqrt{\frac{{\omega }_{c}}{2\hslash {\varepsilon }_{0}V}}\varphi (\overrightarrow{r}),$$
(1)

where ζ is the dipole matrix element for the atomic transition being adressed, ωc is the resonant frequency of the cavity and V the volume of the cavity mode27. The mode volume is defined such that $$V=\int {\varphi }^{2}(\overrightarrow{r}){d}^{3}\overrightarrow{r}$$.

Due to the numerical intensity of the simulations required, we do not perform FDTD simulations including an optical cavity. Instead, loss of light from the guided mode on traversing a microscopic hole is modelled as the introduction of an additional intra-cavity loss mechanism. In this case the decay rate κ is given by2,4,28:

$$\kappa =\frac{c\mathrm{(1}-T\sqrt{{R}_{1}{R}_{2}})}{2{l}_{c}\sqrt{T}{({R}_{1}{R}_{2})}^{\mathrm{1/4}}},$$
(2)

where lc is the optical path length of the cavity, R1 and R2 are the mirror reflectivities and T is the transmission coefficient past the intra-cavity loss source as determined by the FDTD simulations described above.

We assume a 1/e2 intensity radius of 2.5 μm, which is representative of most waveguides of the kind we consider herein, and analyse examples for different cavity lengths. In20 fibre Bragg gratings with a reflectivity of 99.5% were used, and even higher reflectivities are achievable20,21. For now we assume that the mode profile in the hole does not differ significantly from that in the waveguide, although the focal effects of surfaces with convex curvature discussed in the previous section could in principle be used to enhance the coupling strength.

Consider the case of a single Caesium atom addressed on the D2 line (F = 4, mF = 4 → F′ = 5, mF = 5), trapped inside a rectangular void with a length of L = 5 μm inside an optical cavity with length lc = 5 mm. This situation was found to yield a MOTL of (98.7 ± 0.3)%, and applying Eqs (1) and (2) therefore gives values of g1 = 187 MHz and κ = (552 ± 100) MHz respectively. Here g1 clearly exceeds the atomic decay rate of γ = 16.4 MHz29 (where γ is equal to half of the spontaneous decay rate Γ, to allow for the atomic population distribution) and the cooperativity equates to C = 3.9 ± 0.8, thus placing this system within the Purcell regime30. Note that for rectangular holes we consider only losses associated with imperfect MOTL. This is because, in the case of rectangular holes, the reflected light was found to overlap well with the mode of the waveguide and the reflection coefficient could be reduced to ~0.5% through appropriate local tuning of the hole length. When considering holes with other shapes reflection losses are taken into account.

In order to enter the strong coupling regime it is also necessary that g1 > κ. This would be reached for a single Cs atom in a rectangular void of L = 5 μm and a cavity length of lc = 50 mm, again for a cooperativity of C = 3.9 ± 0.8 and a coupling rate of g1 = 59 MHz and κ = (55 ± 10) MHz. For longer rectangular holes, up to a size of L = 8 μm ((96.7 ± 0.3)% MOTL), cooperativities with C = 1.8 ± 0.2 and a cavity length of lc = 300 mm with g1 = 24 MHz and κ = (20.0 ± 1.5) MHz are possible. While introducing a large ensemble of cold atoms into such a space is difficult, introducing a single trapped atom into a hole of this size is plausible, and small rectangular holes may therefore permit strong coupling of single atoms to guided light.

Holes with convex surface curvatures may allow the strong coupling regime to be reached for even larger holes, due to a combination of increased MOTL and local field enhancement by the focal effects of the surfaces. For example, we find that convex, parabolic surface curvature with a coefficient of $$\frac{\delta z}{{r}^{2}}=0.068\,\mu {{\rm{m}}}^{-1}$$ allows a cooperativity of 4 to be achieved for a single Cs atom in a 20 μm long hole. See supplementary material for full details.

When multiple atoms are trapped inside a void and therefore confined in such a cavity, there is a collective enhancement of the coupling constant by a factor equal to the square root of the number of atoms present $${g}_{N}=\sqrt{N}{g}_{1}$$31,32, assuming the atoms all couple equally to the optical field. Considering the trapping volumes involved (~1−1000 μm3) and the densities typically achievable in a dipole trap (~1 μm−3 without evaporative cooling or ~1000 μm−3 with33), atom numbers from 1 to 106 should be achievable, with a corresponding increase in the achievable cooperativity. Calculation of an exact value for the collective cooperativity CN requires specification of both the number and distribution of atoms within the hole. As an example, confinement of 260 Cs atoms within a hole of length 20 μm with convex, parabolic surface curvature with a coefficient of $$\frac{\delta z}{{r}^{2}}=0.068\,\mu {{\rm{m}}}^{-1}$$ could be expected to yield cooperativities on the order of CN = 400, subject to reasonable assumptions about the distribution of the atoms within the hole. See supplementary material for full details.

Other quantum systems such as quantum dots34 or semiconductor vacancy centres35 could be placed into much smaller holes, and potentially even into holes which are then filled with index-matching fluid, as is done in36. Bringing these systems into the strong coupling or Purcell regimes should therefore also be possible in microscopic voids of this kind.

## Outlook

The transmission of light across holes in optical waveguides, with sizes in the range 1 to 30 micrometers, has been studied via numerical simulation. Most attention was given to losses resulting from mode mismatch, since for curved surfaces reflection losses remain roughly constant, at about 8% for two uncoated glass surfaces. The results are found to be consistent with previous experimental results and reproduce the correct limiting behaviour as variables become large or small and calculation of the transmission becomes trivial.

The results show that for a given length of hole the losses due to mode mismatch can be greatly reduced through appropriate hole shaping, with appropriate convex parabolic curvature of the input and output faces of a 20 micrometer long hole reducing losses due to mode-mismatch from ~15% in the case of flat end faces to 0.5(+1.3/−0.5)%. Shaping of holes to maximise power transmission may have applications in fibre-based sensors as well as in quantum optics experiments involving cold atoms.

It is also shown that dipole traps for ultracold atoms can be formed within such holes using only guided light, with maximum depths in the range of ten to fifteen mK for typical silica waveguides and trapping laser detunings of ~200 nm. Furthermore, our calculations suggest that construction of optical cavities around such holes should allow the strong coupling regime to be reached for single atoms trapped in holes up to ~20 μm in length. Exploiting collective enhancement to increase the coupling strength allows the use of larger voids and permits higher cooperativities. This could make holes of this kind an ideal component for interfacing light and cold atoms as part of an integrated quantum information system.

Note that the potential effects of imperfect fabrication are not accounted for in our simulations. Future work will include determining suitable methods for the smoothing and anti-reflection coating of the interior hole surfaces. For example, smoothing is expected to be possible using either ion beam milling or plasma assisted chemical etching37. Additionally, shaping of the waveguide’s refractive index profile on either side of the junction will be investigated. Previous experimental work has demonstrated the plausibility of shaping such waveguides38,39, and the additional dimension this approach adds to the space of free parameters available when designing a waveguide-void interface should allow for extremely high transmission coefficients to be achieved.

## Data Availability

Any relevant data not presented in the manuscript is available from the authors upon reasonable request.

## References

1. Kohnen, M. et al. An array of integrated atom-photon junctions. Nat. Photon. 5(35–38) (2011).

2. Reiserer, A. & Rempe, G. Cavity-based quantum networks with single atoms and optical photons. Rev. Mod. Phys. 87, 1379 (2015).

3. Sorensen, H. et al. Coherent Backscattering of Light Off One-Dimensional Atomic Strings. PRL 117(133604) (2016).

4. Vetsch, E. et al. Optical Interface Created by Laser-Cooled Atoms Trapped in the Evanescent Field Surrounding an Optical Nanofiber. PRL 104(203603) (2010).

5. Daly, M., Truong, V., Phelan, C., Deasy, K. & Nic Chormaic, S. Nanostructured optical nanofibres for atom trapping. N. J. Phys. 16(053052) (2014).

6. Pechkis, J. & Fatemi, F. Cold atom guidance in a capillary using bluedetuned, hollow optical modes. Optics Express 20(13409) (2012).

7. Bajcsy, M. et al. Efficient All-Optical Switching Using Slow Light within a Hollow Fiber. PRL 102(203902) (2009).

8. Christensen, C. et al. Trapping of ultracold atoms in a hollow-core photonic crystal fiber. PRA 78(033429) (2008).

9. Jaksch, D. et al. Fast Quantum Gates for Neutral Atoms. PRL 85(2208) (2000).

10. Urban, E. et al. Observation of Rydberg blockade between two atoms. Nature Physics 5(110) (2009).

11. Petrosyan, D., Motzoi, F., Saffman, M. & Molmer, K. High-fidelity Rydberg quantum gate via a two-atom dark state. PRA 96(042306) (2017).

12. Huang, H., Yang, L. & Liu, J. Micro-hole drilling and cutting using femtosecond fiber laser. Optical engineering 53(051513) (2014).

13. Goya, K., Itoh, T., Seki, A. & Watanabe, K. A Through-hole Array on Optical Fibers Fabricated by 1-kHz/400-nm Femtosecond Laser Pulses for an in-line/pico-Litter Spectrometer Design. Procedia engineering 87(919) (2014).

14. Workshop of photonics website, http://www.wophotonics.com/.

15. Stewarta, G., Tandyb, C., Moodiec, D., Moranted, M. & Donga, F. Design of a fibre optic multi-point sensor for gas detection. Sensors and Actuators B: Chemical 51(227) (1998).

16. Jin, W., Ho, H., Cao, Y., Ju, J. & Qi, L. Gas detection with micro- and nano-engineered optical fibers. Optical Fiber Technology 19(741) (2013).

17. Yuan, L. et al. All-in-fiber optofluidic sensor fabricated by femtosecond laser assisted chemical etching. Optics Letters 39(2358) (2014).

18. Martinez, A., Zhou, K., Bennion, I. & Yamashita, S. In-fiber microchannel device filled with a carbon nanotube dispersion for passive mode-lock lasing. Optics Express 16(15425) (2008).

19. Optiwave website, https://optiwave.com/applications/fdtd-application-overview/.

20. Kato, S. & Aoki, T. Strong Coupling between a Trapped Single Atom and an All-Fiber Cavity. Phys. Rev. Lett. 115(093603) (2015).

21. Keloth, J., Nayak, K. & Hakuta, K. Fabrication of a centimeter-long cavity on a nanofiber for cavity quantum electrodynamics. Opt. Lett. 42(1003–1006) (2017).

22. Yalla, R., Sadgrove, M., Nayak, K. & Hakuta, K. Cavity Quantum Electrodynamics on a Nanofiber Using a Composite Photonic Crystal Cavity. Phys. Rev. Lett. 113(143601) (2014).

23. Horak, P. et al. Possibility of single-atom detection on a chip. Phys. Rev. A 67(043806) (2003).

24. Le Kien, F. & Hakuta, K. Cavity-enhanced channeling of emission from an atom into a nanofiber. Phys. Rev. A 80(053826) (2009).

25. Meltz, G., Morey, W. & Glenn, W. Formation of Bragg gratings in optical fibers by a transverse holographic method. Opt. Lett. 14(823) (1989).

26. Zhang, X., Xu, C. & Ren, Z. High fidelity heralded single-photon source using cavity quantum electrodynamics. Scientific Reports 8(3140) (2018).

27. Kimble, H. Strong Interactions of Single Atoms and Photons in Cavity QED. Physica Scripta T76(127) (1998).

28. Saleh, B. & Teich, M. Fundamentals of Photonics. Wiley (2007).

29. Steck, D. Alkali D Line Data. (1998).

30. Gérard, J. et al. Enhanced spontaneous emission by quantum boxes in a monolithic optical microcavity. Phys. Rev. Lett. 81, 1110–1113 (1998).

31. Hernandez, G., Zhang, J. & Zhu, Y. Collective coupling of atoms with cavity mode and free-space field. Optics Express 17(4798) (2009).

32. Guerlin, C., Brion, E., Esslinger, T. & Molmer, K. Cavity quantum electrodynamics with a Rydberg-blocked atomic ensemble. Phys. Rev. A 82(053832) (2010).

33. Chaudhuri, S., Roy, S. & Unnikrishnan, C. Evaporative Cooling of Atoms to Quantum Degeneracy in an Optical Dipole Trap. J. Phys.: Conf. Ser. 80(012036) (2007).

34. Loss, D. & DiVincenzo, D. Quantum computation with quantum dots. Phys. Rev. A 57(120) (1998).

35. Jelezko, F. & Wrachtrup, J. Single defect centres in diamond: A review. Phys. Stat. Sol. A 203(3207) (2006).

36. Lai, Y., Zhou, K. & Bennion, I. Microchannels in conventional single-mode fibers. Opt. Lett. 31(2559) (2006).

37. Zarowin, C. Comparison of the smoothing and shaping of optics by plasma-assisted chemical etching and ion milling using the surface evolution theory. Applied Optics 32(2984) (1993).

38. Pertsch, T. et al. Discrete diffraction in two-dimensional arrays of coupled waveguides in silica. Optics Letters 29(5) (2004).

39. Szameit, A. et al. Discrete nonlinear localization in femtosecond laser written waveguides in fused silica. Optics Express 13(10552) (2005).

## Acknowledgements

This work was supported by the Engineering and Physical Sciences Research Council [grants EP/R024111/1, EP/M013294/1] and by the European Comission [grants 295293, 800942] (“QuILMI” and “ErBeStA”). The authors would like to thank Joerg Goette for useful discussions.

## Author information

Authors

### Contributions

L.H. and N.C. provided the initial ideas for the work. C.B. commenced the simulation work, which was then significantly expanded by N.C. and E.D. M.T.G. provided advice on the efficient use of the simulation software. E.D., V.N. and L.H. assisted N.C. with manuscript preparation and review of the relevant literature. All authors reviewed the final manuscript.

### Corresponding author

Correspondence to N. Cooper.

## Ethics declarations

### Competing Interests

The authors declare no competing interests.

Publisher’s note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Rights and permissions

Reprints and Permissions

Cooper, N., Da Ros, E., Briddon, C. et al. Prospects for strongly coupled atom-photon quantum nodes. Sci Rep 9, 7798 (2019). https://doi.org/10.1038/s41598-019-44292-2

• Accepted:

• Published:

• DOI: https://doi.org/10.1038/s41598-019-44292-2


text:
# Capacity of a conductor does not depend on the nature of the material of the conductor. Why?

Dear Student,
capacity of a conductor ,$C=\frac{Q}{V}$
where,Q=charge on the conductor and V=voltage
Q and V do not depend on the material of the conductor,so the capacity also does not depend upon the material of the conductor.
Hope this information will clear your doubts about topic.

If you have any more doubts just ask here on the forum and our experts will try to help you out as soon as possible.

Regards

• 2
What are you looking for?


text:
# How do you simplify 2^2*2^3?

Nov 9, 2016

${2}^{2} \cdot {2}^{3} \implies {2}^{2 + 3} \implies {2}^{5}$

#### Explanation:

When mutliplying similar terms with exponents you add the exponents.

${2}^{2} \cdot {2}^{3} \implies {2}^{2 + 3} \implies {2}^{5}$

The displayable reason is:

${2}^{2} = 2 \cdot 2$

${2}^{3} = 2 \cdot 2 \cdot 2$

Therefore ${2}^{2} \cdot {2}^{3} \implies 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \implies {2}^{5}$

Nov 9, 2016

$32$

#### Explanation:

We can simplify by expressing each of the products in their numeric form.

${2}^{2} \times {2}^{3} = 4 \times 8 = 32$

OR by simplifying the product using $\textcolor{b l u e}{\text{law of exponents}}$

$\textcolor{\mathmr{and} a n \ge}{\text{Reminder }} \textcolor{red}{\overline{\underline{| \textcolor{w h i t e}{\frac{2}{2}} \textcolor{b l a c k}{{a}^{m} \times {a}^{n} = {a}^{m + n}} \textcolor{w h i t e}{\frac{2}{2}} |}}}$

$\Rightarrow {2}^{2} \times {2}^{3} = {2}^{2 + 3} = {2}^{5} = 32$


text:
# 1.2 Data Representation in a Computer

Computer must not only be able to carry out computations, they must be able to do them quickly and efficiently. There are several data representations, typically for integers, real numbers, characters, an

Computer must not only be able to carry out computations, they must be able to do them quickly and efficiently. There are several data representations, typically for integers, real numbers, characters, and logical values.

### Number Representation in Various Numeral Systems

A numeral system is a collection of symbols used to represent small numbers, together with a system of rules for representing larger numbers. Each numeral system uses a set of digits. The number of various unique digits, including zero, that a numeral system uses to represent numbers is called base or radix.

#### Base – b numeral system

b basic symbols (or digits) corresponding to natural numbers between 0 and b − 1 are used in the representation of numbers.

To generate the rest of the numerals, the position of the symbol in the figure is used. The symbol in the last position has its own value, and as it moves to the left its value is multiplied by b.

We write a number in the numeral system of base b by expressing it in the form

N(b), with n+1 digit for integer and m digits for fractional part, represents the sum:

Decimal, Binary, Octal and Hexadecimal are common used numeral system. The decimal system has ten as its base. It is the most widely used numeral system, because humans have four fingers and a thumb on each hand, giving total of ten digit over both hand.

Switches, mimicked by their electronic successors built of vacuum tubes, have only two possible states: “open” and “closed”. Substituting open=1 and closed=0 yields the entire set of binary digits. Modern computers use transistors that represent two states with either high or low voltages. Binary digits are arranged in groups to aid in processing, and to make the binary numbers shorter and more manageable for humans.Thus base 16 (hexadecimal) is commonly used as shorthand. Base 8 (octal) has also been used for this purpose.

Decimal System

Decimal notation is the writing of numbers in the base-ten numeral system, which uses various symbols (called digits) for no more than ten distinct values (0, 1, 2, 3, 4, 5, 6, 7, 8 and 9) to represent any number, no matter how large. These digits are often used with a decimal separator which indicates the start of a fractional part, and with one of the sign symbols + (positive) or − (negative) in front of the numerals to indicate sign.

Decimal system is a place-value system. This means that the place or location where you put a numeral determines its corresponding numerical value. A two in the one’s place means two times one or two. A two in the one-thousand’s place means two times one thousand or two thousand.

The place values increase from right to left. The first place just before the decimal point is the one’s place, the second place or next place to the left is the ten’s place, the third place is the hundred’s place, and so on.

The place-value of the place immediately to the left of the “decimal” point is one in all place-value number systems. The place-value of any place to the left of the one’s place is a whole number computed from a product (multiplication) in which the base of the number system is repeated as a factor one less number of times than the position of the place.

For example, 5246 can be expressed like in the following expressions

The place-value of any place to the right of the decimal point is a fraction computed from a product in which the reciprocal of the base—or a fraction with one in the numerator and the base in the denominator—is repeated as a factor exactly as many times as the place is to the right of the decimal point.

For example

#### Binary System

The binary number system is base 2 and therefore requires only two digits, 0 and 1. The binary system is useful for computer programmers, because it can be used to represent the digital on/off method in which computer chips and memory work.

A binary number can be represented by any sequence of bits (binary digits), which in turn may be represented by any mechanism capable of being in two mutually exclusive states.

Counting in binary is similar to counting in any other number system. Beginning with a single digit, counting proceeds through each symbol, in increasing order. Decimal counting uses the symbols 0 through 9, while binary only uses the symbols 0 and 1.

When the symbols for the first digit are exhausted, the next-higher digit (to the left) is incremented, and counting starts over at 0A single bit can represent one of two values, 0 or 1.Binary numbers are convertible to decimal numbers.

Here’s an example of a binary number, 11101.11(2)MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaaigdacaaIXaGaaGymaiaaicdacaaIXaGaaiOlaiaaigdacaaIXaWaaSbaaSqaaiaacIcacaaIYaGaaiykaaqabaaaaa@3DF1@ , and its representation in the decimal notation

The hexadecimal system is base 16. Therefore, it requires 16 digits. The digits 0 through 9 are used, along with the letters A through F, which represent the decimal values 10 through 15. Here is an example of a hexadecimal number and its decimal equivalent:

The hexadecimal system (often called the hex system) is useful in computer work because it is based on powers of 2. Each digit in the hex system is equivalent to a four-digit binary number. Table below shows some hex/decimal/binary equivalents.

 Hexadecimal Digit Decimal Equivalent Binary Equivalent 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111 10 16 10000 F0 240 11110000 FF 255 11111111

#### Octal System

Binary is also easily converted to the octal numeral system, since octal uses a radix of 8, which is a power of two (namely, 23, so it takes exactly three binary digits to represent an octal digit). The correspondence between octal and binary numerals is the same as for the first eight digits of hexadecimal in the table above. Binary 000 is equivalent to the octal digit 0, binary 111 is equivalent to octal 7, and so forth.

Converting from octal to binary proceeds in the same fashion as it does for hexadecimal:

And from octal to decimal:

#### Converting from decimal to base–b

After that, multiply the fractional part by b repeatedly to get each digit as an integer part. We will continue this process until we get a zero as our fractional part or until we recognize an infinite repeating pattern.

Now convert 0.625 to hexadecimal :

.

0.39625 * 16 = 0.625 ————————————-> 0

.625* 16 = 10 —————————> A.

We get fractional part is zero.

### Data Representation in a Computer. Units of Information

#### Basic Principles

Data Representation refers to the methods used internally to represent information stored in a computer. Computers store lots of different types of information:

• numbers
• text
• graphics of many varieties (stills, video, animation)
• sound

At least, these all seem different to us. However, all types of information stored in a computer are stored internally in the same simple format: a sequence of 0’s and 1’s. How can a sequence of 0’s and 1’s represent things as diverse as your photograph, your favorite song, a recent movie, and your term paper?

• Numbers must be expressed in binary form following some specific standard.
• Character data are assigned a sequence of binary digits
• Other types of data, such as sounds, videos or other physical signals are converted to digital following the schema below

Digital signal

Depending on the nature of its internal representation, data items are divided into:

• Basic types (simple types or type primitives) : the standard scalar predefined types that one would expect to find ready for immediate use in any programming language
• Structured types(Higher level types) are then made up from such basic types or other existing higher level types.

#### Units of Information

The most basic unit of information in a digital computer is called a BIT, which is a contraction of Binary Digit. In the concrete sense, a bit is nothing more than a state of “on” or “off” (or “high” and “low”) within a computer circuit. In 1964, the designers of the IBM System/360 mainframe computer established a convention of using groups of 8 bits as the basic unit of addressable computer storage. They called this collection of 8 bits a byte.

Computer words consist of two or more adjacent bytes that are sometimes addressed and almost always are manipulated collectively. The word size represents the data size that is handled most efficiently by a particular architecture. Words can be 16 bits, 32 bits, 64 bits, or any other size that makes sense within the context of a computer’s organization.

Some other units of information are described in the following table :

Representation of Integers

An integer is a number with no fractional part; it can be positive, negative or zero. In ordinary usage, one uses a minus sign to designate a negative integer. However, a computer can only store information in bits, which can only have the values zero or one. We might expect, therefore, that the storage of negative integers in a computer might require some special technique – allocating one sign bit (often the most significant bit) to represent the sign: set that bit to 0 for a positive number, and set to 1 for a negative number.

#### Unsigned Integers

Unsigned integers are represented by a fixed number of bits (typically 8, 16, 32, and/or 64)

• With 8 bits, 0…255 (0016…FF16) can be represented;
• With 16 bits, 0…65535 (000016…FFFF16) can be represented;
• In general, an unsigned integer containing n bits can have a value between 0 and 2n1MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaaikdadaahaaWcbeqaaiaad6gaaaGccqGHsislcaaIXaaaaa@3970@

If an operation on bytes has a result outside this range, it will cause an ‘overflow’

#### Signed Integers

The binary representation discussed above is a standard code for storing unsigned integer numbers. However, most computer applications use signed integers as well; i.e. the integers that may be either positive or negative.

In binary we can use one bit within a representation (usually the most significant or leading bit) to indicate either positive (0) or negative (1), and store the unsigned binary representation of the magnitude in the remaining bits.

However, for reasons of ease of design of circuits to do arithmetic on signed binary numbers (e.g. addition and subtraction), a more common representation scheme is used called two’s complement. In this scheme, positive numbers are represented in binary, the same as for unsigned numbers. On the other hand, a negative number is represented by taking the binary representation of the magnitude:

• Complement the bits : Replace all the 1’s with 0’s, and all the 0’s with 1’s;
• Add one to the complemented number.

Example

+4210 =  001010102
and so
-4210   =  110101102

• Binary number with leading 0 is positive
• Binary number with leading 1 is negative

Example

Performing two’s complement on the decimal 42 to get -42

Using a eight-bit representation

42= 00101010   Convert to binary

11010101   Complement the bits

11010101   Add 1 to the complement
+ 00000001
--------
11010110  Result is  -42 in two's complement

### Arithmetic Operations on Integers

#### Addition and Subtraction of integers

Addition and subtraction of unsigned binary numbers

Binary Addition is much like normal everyday (decimal) addition, except that it carries on a value 2 instead of value 10.

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0, and carry 1 to the next more significant bit

Example

00011010 + 00001100 = 00100110
1 1	            carries
0 0 0 1 1 0 1 0	=   26(base 10)
+  0 0 0 0 1 1 0 0	=   12(base 10)
----------------
0 0 1 0 0 1 1 0	=   38(base 10)

11010001 + 00111110 = 100011010

1 1           1	      carries
1 1 0 1 0 0 0 1	 =    208 (base 10)
+ 0 1 0 0 1 0 0 1	 =    73 (base 10)
----------------
1 0 0 0 1 1 0 1 0     =    281 (base 10)

The result exceeds the magnitude which can be represented with 8 bits. This is an overflow.

Subtraction is executed by using two’s complement

Addition and subtraction of signed binary numbers

#### Multiplication and Division of Integers

Binary Multiplication

Multiplication in the binary system works the same way as in the decimal system:

0 x 0 = 0

0 x 1 = 0

1 x 0 = 0

1 x 1 = 1, and no carry or borrow bits

Example

00101001 × 00000110 = 11110110

0  0  1  0  1  0  0  1	   =   	41(base 10)
×     0  0  0  0  0  1  1  0	   =   	6(base 10)
----------------------
0  0  0  0  0  0  0
0  1  0  1  0  0  1
0  1  0  1  0  0  1
----------------------------
0  0  1  1  1  1  0  1  1  0	   =   	246(base 10)

00010111 × 00000011 = 01000101

0  0  0  1  0  1  1  1	   =   	23(base 10)
×     0  0  0  0  0  0  1  1	   =   	3(base 10)
----------------------
1  1  1  1  1      	 	carries
0  0  1  0  1  1  1
0  0  1  0  1  1  1
0  0  1  0  0  0  1  0  1	   =   	69(base 10)

Binary division follow the same rules as in decimal division.

### Logical operations on Binary Numbers

Logical Operation with one or two bits

NOT : Changes the value of a single bit. If it is a “1”, the result is “0”; if it is a “0”, the result is “1”.

AND: Compares 2 bits and if they are both “1”, then the result is “1”, otherwise, the result is “0”.

OR : Compares 2 bits and if either or both bits are “1”, then the result is “1”, otherwise, the result is “0”.

XOR : Compares 2 bits and if exactly one of them is “1” (i.e., if they are different values), then the result is “1”; otherwise (if the bits are the same), the result is “0”.

Logical operators between two bits have the following truth table

 x y x AND y x OR y x XOR y 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0

Logical Operation with one or two binary numbers

A logical (bitwise) operation operates on one or two bit patterns or binary numerals at the level of their individual bits.

Example

NOT 0111
= 1000

AND operation

An AND operation takes two binary representations of equal length and performs the logical AND operation on each pair of corresponding bits. In each pair, the result is 1 if the first bit is 1 AND the second bit is 1. Otherwise, the result is 0.

Example

     0101
AND  0011
= 0001

OR operation

An OR operation takes two bit patterns of equal length, and produces another one of the same length by matching up corresponding bits (the first of each; the second of each; and so on) and performing the logical OR operation on each pair of corresponding bits.

Example

      0101
OR 0011
= 0111

XOR Operation

An exclusive or operation takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits.

Example

0101
XOR 0011
= 0110

### Symbol Representation

#### Basic Principles

It is important to handle character data. Character data is not just alphabetic characters, but also numeric characters, punctuation, spaces, etc. They need to be represented in binary.

There aren’t mathematical properties for character data, so assigning binary codes for characters is somewhat arbitrary.

ASCII Code Table

ASCII stands for American Standard Code for Information Interchange. The ASCII standard was developed in 1963, permitted machines from different manufacturers to exchange data.

ASCII code table consists of 128 binary values (0 to 127), each associated with a character or command. The non-printing characters are used to control peripherals such as printer.

The extended ASCII character set also consists 128 128 characters representing additional special, mathematical, graphic and foreign characters.

#### Unicode Code Table

There are some problems with the ASCII code table. With ASCII character set, string datatypes allocated one byte per character. But logographic languages such as Chinese, Japanese, and Korean need far more than 256 characters for reasonable representation. Even Vietnamese, a language uses almost Latin letters, need 61 characters for representation. Where can we find numbers for our characters? is it a solution : 2 bytes per character?

Hundreds of different encoding systems were invented. But these encoding systems conflict with one another : two encodings can use the same number for two different characters, or use different numbers for the same character.

The Unicode standard was first published in 1991. With two bytes for each character, it can represent 216-1 different characters.

The Unicode standard has been adopted by such industry leaders as HP, IBM, Microsoft, Oracle, Sun, and many others. It is supported in many operating systems, all modern browsers, and many other products.

The obvious advantages of using Unicode are :

• To offer significant cost savings over the use of legacy character sets.
• To enable a single software product or a single website to be targeted across multiple platforms, languages and countries without re-engineering.
• To allow data to be transported through many different systems without corruption.

### Representation of Real Numbers

#### Basic Principles

No human system of numeration can give a unique representation to real numbers. If you give the first few decimal places of a real number, you are giving an approximation to it.

Mathematicians may think of one approach : a real number x can be approximated by any number in the range from x – epsilon to x + epsilon. It is fixed-point representation. Fixed-point representations are unsatisfactory for most applications involving real numbers.

Scientists or engineers will probably use scientific notation: a number is expressed as the product of a mantissa and some power of ten.

A system of numeration for real numbers will typically store the same three data — a sign, a mantissa, and an exponent — into an allocated region of storage

The analogues of scientific notation in computer are described as floating-point representations.

In the decimal system, the decimal point indicates the start of negative powers of 10.

If we are using a system in base k (ie the radix is k), the ‘radix point’ serves the same function:

A floating point representation allows a large range of numbers to be represented in a relatively small number of digits by separating the digits used for precision from the digits used for range.

To avoid multiple representations of the same number floating point numbers are usually normalized so that there is only one nonzero digit to the left of the ‘radix’ point, called the leading digit.

A normalized (non-zero) floating-point number will be represented using

where

• s is the sign,
• b is the base (or radix)

Example

If k = 10 (base 10) and p = 3, the number 0·1 is represented as 0.100

If k = 2 (base 2) and p = 24, the decimal number 0·1 cannot be represented exactly but is approximately 110011001100110011001101×24MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaabgdacaGG3cGaaeymaiaaicdacaaIWaGaaeymaiaabgdacaaIWaGaaGimaiaabgdacaqGXaGaaGimaiaaicdacaqGXaGaaeymaiaaicdacaaIWaGaaeymaiaabgdacaaIWaGaaGimaiaabgdacaqGXaGaaGimaiaabgdacqGHxdaTcaaIYaWaaWbaaSqabeaacqGHsislcaaI0aaaaaaa@4CEA@

Formally,

In brief, a normalized representation of a real number consist of

• The range of the number : the number of digits in the exponent (i.e. by emaxMathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadwgadaWgaaWcbaGaciyBaiaacggacaGG4baabeaaaaa@39CC@ ) and the base b to which it is raised
• The precision : the number of digits p in the significand and its base b

#### IEEE 754/85 Standard

There are many ways to represent floating point numbers. In order to improve portability most computers use the IEEE 754 floating point standard.

There are two primary formats:

• 32 bit single precision.
• 64 bit double precision.

Single precision consists of:

• A single sign bit, 0 for positive and 1 for negative;
• An 8 bit base-2 (b = 2) excess-127 exponent, with eminMathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadwgadaWgaaWcbaGaciyBaiaacMgacaGGUbaabeaaaaa@39CA@ = –126 (stored as 127(10)126(10)=1=00000001(2) ) and emax = 127 (stored as 127(10)+127(10)=254(10)=11111110(2) ).
• a 23 bit base-2 (k=2) significand, with a hidden bit giving a precision of 24 bits (i.e. 1.d1d2d23 )

Notes

• Single precision has 24 bits precision, equivalent to about 7.2 decimal digits.
• The largest representable non-infinite number is almost 2×21273.402823×1038
• The smallest representable non-zero normalized number is 1×21271.17549×1038
• Denormalized numbers (eg 0.01×2126 ) can be represented.
• There are two zeros, ± 0.
• There are two infinities, ± .
• A NaN (not a number) is used for results from undefined operations

Double precision floating point standard requires a 64 bit word

• The first bit is the sign bit
• The next eleven bits are the exponent bits
• The final 52 bits are the fraction

Range of double numbers : [±2.225×10−308÷±1.7977×10308]