text:
## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 21 February 2020

###### Hasso-Plattner-Institute, University of Potsdam, Germany
Job Posting

The Cybersecurity - Identity Management group at the Hasso-Plattner-Institute (HPI), University of Potsdam is seeking to fill several PhD and PostDoc positions in the area of cryptography and privacy.

• Development of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
• Distributed identity management
• Privacy-enhancing technologies
• Foundations and solutions for real-world cryptography
• Publish and present results at top-tier international conferences
• Participate in teaching activities
• Master's degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment
• Profound knowledge in the areas of cryptography and IT security (for postdoctoral candidates proven in the form of publications in these areas)
• Excellent English language skills
What we offer
• Collaborative work environment in a newly established research group
• Outstanding setting to conduct top academic research with strong connections to industry
• Working at the HPI campus in Potsdam-Babelsberg (S-Bahn station Griebnitzsee) near to Berlin

We look forward to your application including two references, motivation letter and copies of relevant diplomas and certificates. Please submit your application documents (only as PDF) via email.

Closing date for applications:

Contact: Anja Lehman, email: anja.lehmann (at) hpi.de

###### Telecom SudParis, RST Department CNRS UMR 5157, SAMOVAR/R3S and IRT SytemX
Job Posting
The cryptographic protocols mainly comprise functionalities such as public-key encryption, digital signatures, and key exchange. These cryptographic protocols are based on the difficulty of certain mathematical operations, such as finding the prime factors of a very large integer. However, recent advances in quantum computing mean that these difficult math problems might soon be solved efficiently, with a potentially serious impact upon our security. Realizing the availability of quantum computers from research labs to general purpose use in the near future, the preparation against such a threat has taken shape recently, and happening to be a fast growing topic of research referred as post-quantum cryptography (PQC). Nowadays, certain candidate families of post-quantum schemes have been realized including code-based, hash-based, multivariate, lattice-based and supersingular isogeny-based. Security of all these primitives are based on different mathematical problems which are believed to be hard even with respect to quantum computation and quantum communications. In this project, we aim to achieve the following goals: • To study the existing PQC schemes and demonstrate state of the art PQC following an extensive review. • To propose post-quantum schemes taking in account their possible application to IoT security or Blockchain.

Closing date for applications:

Contact: joaquin.garcia_alfaro@telecom-sudparis.eu and Kalpana.SINGH@irt-systemx.fr

###### University of Clermont-Auvergne, France
Job Posting
Constraint Programming for Cryptanalysis of Symmetric Encryption Schemes
• Location: LIMOS, Clermont-Ferrand, France
• Salary: 2000€
• Duration: 1 year
• Keywords: Cryptanalysis symmetric, constraint programming, SAT solving, ILP.
• Starting date: As soon as possible, when we have a good candidate; at least before October 2020.
• A PhD in Computer Science, Applied Mathematics, Cryptography or related field.
• Competitive research record in symmetric cryptography or in constraint programming.
• Commitment, team working and a critical mind.
• Good written and verbal communication skills in English are essential.

This post-doc is founded by the ANR project Decrypt started in January 2019.

Transforming a theoretical cryptanalysis into a SAT problem or into a set of linear constraints could be a hard and time-consuming task. Our aim is to use constraint programming (CP) to simplify the way the symmetric key attacks are modeled and thus to overpass existing cryptanalytic results. Preliminary studies are really encouraging.

Goal

The main goal is to identify schemes and attacks for which it is possible to use off-the-shelf CP, SAT or ILP approaches. To achieve this goal, the work will be divided into the following tasks.

1. Study symmetric encryption schemes and identify for several schemes the different components that are used in the scheme design.
2. Design CP, SAT, and ILP models for cryptanalytic problems on selected schemes. We will mainly focus on the following attacks: cube attacks, conditional cube attacks with division property, (related-key) differential and linear cryptanalysis, word-based division property / integral distinguisher.
3. Experimentally evaluate CP, SAT, and ILP solvers on the models designed in previous tasks, and compare these solvers with existing dedicated cryptanalysis approaches. Design of a tool to automate this task is one of the goals of the project.

Closing date for applications:

###### Université Jean Monnet, Saint-Etienne, France
Job Posting
A Ph.D. position is open in université Jean Monnet. This Ph.D project aims to develop novel techniques that can protect cryptographic implementations against side-channel attacks and fault attacks. The protection studied will be mainly algorithmic protection, with experimental evaluation of their effectiveness and efficiency. Various directions can be explored with respect to the candidate background.

Closing date for applications:

Contact: Vincent Grosso

Job Posting
PQSecure Technologies, LLC is a growing startup company active in the area of post-quantum cryptographic engineering with focus on embedded and IoT devices. PQSecure is currently funded by National Science Foundation SBIR Phase II fund and is an active participant of National Institute of Standards and technology (NIST) for post-quantum cryptography. We are looking for a postdoc/research scientist with post-quantum cryptography and implementations experience and relevant publication records. Candidates should hold a PhD in Computer science/engineering, or electrical engineering, or applied mathematics with excellent programming skills and cryptographic protocol design. PQSecure offers a competitive hiring package including, 401k, health insurance, stock option, 3 weeks of PTO, travel reimbursement for relevant conferences, and etc.). The position is for one year with possibility of renewal based on the performance of the candidate. The salary will be $87,000 per year. PQSecure is located in the beautiful city Boca Raton, FL. The deadline for applications is February 15, 2020. The position will be open until filled. Closing date for applications: Contact: Dr. Reza Azarderakhsh razarder[a/t]pqsecurity.com ###### Junichi Tomida, Nuttapong Attrapadung ePrint Report At Eurocrypt'19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner (including those that resolved some open problems at the time). However, his approach heavily relies on so-called q-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem. In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung. Our framework significantly expands an area of ABEs that are realizable from standard assumptions. This includes the following adaptively secure large-universe ABEs for Boolean formulae under MDDH. -- The first completely unbounded monotone key-policy (KP)/ciphertext-policy (CP) ABE. Previously, such ABE has been only recently proposed, but only for the KP and small-universe flavor (Kowalczyk and Wee, Eurocrypt'19). -- The first completely unbounded non-monotone KP/CP-ABE. Especially, our ABEs support a new type of non-monotonicity that subsumes previous two types of non-monotonicity, namely, by Ostrovsky et al. (CCS'07) and by Okamoto and Takashima (CRYPTO'10). -- The first non-monotone KP and CP-ABE with constant-size ciphertexts and secret keys, respectively. -- The first monotone KP and CP-ABE with constant-size secret keys and ciphertexts, respectively. ###### Changmin Lee, Alexandre Wallet ePrint Report In ASIACRYPT 2019, Genise et al. describe GGH+19 a new somewhat homomorphic encryption scheme. The security relies on an inhomogeneous and non-structured variant of the NTRU assumption that they call MiNTRU. To allow for meaningful homomorphic computations, they use overstretched parameters, but they do not provide an analysis of their new assumption against the state-of-the-art attack of Kirchner and Fouque KF17 for overstretched modulus. We show that the parameters of GGH+19 do not satisfy the desired security by actually conducting the known analysis. We also report a successful break of the smallest set of parameters in around 15 hours of computations while they are claimed to reach 100 bits of security. ###### Itai Dinur ePrint Report We consider a \emph{collision search problem} (CSP), where given a parameter$C$, the goal is to find$C$collision pairs in a random function$f:[N] \rightarrow [N]$(where$[N] = \{0,1,\ldots,N-1\})$using$S$bits of memory. Algorithms for CSP have numerous cryptanalytic applications such as space-efficient attacks on double and triple encryption. The best known algorithm for CSP is \emph{parallel collision search} (PCS) published by van Oorschot and Wiener, which achieves the time-space tradeoff$T^2 \cdot S = \tilde{O}(C^2 \cdot N)$. In this paper, we prove that any algorithm for CSP satisfies$T^2 \cdot S = \tilde{\Omega}(C^2 \cdot N)$, hence the best known time-space tradeoff is optimal (up to poly-logarithmic factors in$N$). On the other hand, we give strong evidence that proving similar unconditional time-space tradeoff lower bounds on CSP applications (such as breaking double and triple encryption) may be very difficult, and would imply a breakthrough in complexity theory. Hence, we propose a new restricted model of computation and prove that under this model, the best known time-space tradeoff attack on double encryption is optimal. ###### Shweta Agrawal, Shota Yamada ePrint Report Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only bilinear maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of “Obfustopia”. Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties – its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model. ###### Yindong Chen, Limin Lin, Chuliang Wei ePrint Report Let$k \ge 2$be an integer, define $S_t^k:=\Bigg\{(a,b)\in \mathbb{Z}^2\ \Big| \ { 0 \le a,b \le 2^{k}-2,\ a+b\equiv t ~(\text{mod} \ 2^k-1),\ \w(a)+\w(b)\le{k-1}}\Bigg\},$ where$t \in \mathbb{Z}, 1 \le t \le 2^k-2$. This paper gives the upper bound of cardinality of$S_t^k$when$\w(t)\le 10$, proving that a conjecture proposed by Tu and Deng in the case. ###### Meher Krishna Duggirala . , . Ravi Duggirala . , . Krishna Subba Rao Pulugurtha ePrint Report In this paper, a multivariate polynomial and exponential mappings based password protocol is presented. The method can be utilized in public domains. The key generator generates a vector, intended to be used as a password by the authentication protocol subsequently, such that when the vector is substituted and evaluated in certain fixed multivariate polynomials -- that may be listed in a public domain -- the value$0$is found as a result of proper authentication. The public domain in this context could be internal to a large, and possibly distributed, system. The key generator can take hints from the owner of the password to generate the particular zero vector to suit the user. It may take into consideration biometric and any other user specific information at the time of key generation. The information collected by the key generator can be saved by the owner of the password for its possible retrieval upon requisition by the user, during the period of its validity, in case it is forgotten by the user. ###### Lior Rotem, Gil Segev, Ido Shahaf ePrint Report Despite the fundamental importance of delay functions, underlying both the classic notion of a time-lock puzzle and the more recent notion of a verifiable delay function, the only known delay function that offers both sufficient structure for realizing these two notions and a realistic level of practicality is the iterated squaring'' construction of Rivest, Shamir and Wagner. This construction, however, is based on rather strong assumptions in groups of hidden orders, such as the RSA group (which requires a trusted setup) or the class group of an imaginary quadratic number field (which is still somewhat insufficiently explored from the cryptographic perspective). For more than two decades, the challenge of constructing delay functions in groups of known orders, admitting a variety of well-studied instantiations, has eluded the cryptography community. In this work we prove that there are no constructions of generic-group delay functions in cyclic groups of known orders: We show that for any delay function that does not exploit any particular property of the representation of the underlying group, there exists an attacker that completely breaks the function's sequentiality when given the group's order. As any time-lock puzzle and verifiable delay function give rise to a delay function, our result holds for these two notions we well, and explains the lack of success in resolving the above-mentioned long-standing challenge. Moreover, our result holds even if the underlying group is equipped with a$d$-linear map, for any constant$d \geq 2$(and even for super-constant values of$d$under certain conditions). ###### Mihir Bellare, Igors Stepanovs ePrint Report At the core of Apple's iMessage is a signcryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. This motivates us to formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the signcryption scheme itself, with respect to definitions of signcryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage. ###### Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa ePrint Report A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is that the proof size is multiplicative in the circuit size computing the NP relation. That is, the proof size grows by$O(|C|\lambda)$, where$C$is the circuit for the NP relation and$\lambda$is the security parameter. By now, there have been numerous follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static$q$-type assumption. Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem. Our main result is a construction of a pairing-based NIZK for all of NP whose proof size is additive in$|C|$, that is, the proof size only grows by$|C| +\poly(\lambda)$, based on the decisional linear (DLIN) assumption. Since the DLIN assumption is the same assumption underlying GOS-NIZK, our NIZK is a strict improvement on their proof size. As by-products of our main result, we also obtain the following two results: (1) We construct a perfectly zero-knowledge NIZK (NIPZK) for NP relations computable in NC1 with proof size$|w| \cdot \poly(\lambda)$where$|w|$is the witness length based on the DLIN assumption. This is the first pairing-based NIPZK for a non-trivial class of NP languages whose proof size is independent of$|C|$based on a standard assumption. (2)~We construct a universally composable (UC) NIZK for NP relations computable in NC1 in the erasure-free adaptive setting whose proof size is$|w| \cdot \poly(\lambda)$from the DLIN assumption. This is an improvement over the recent result of Katsumata, Nishimaki, Yamada, and Yamakawa (CRYPTO'19), which gave a similar result based on a non-static$q$-type assumption. The main building block for all of our NIZKs is a constrained signature scheme with decomposable online-offline efficiency. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest. ###### Dan Boneh, Saba Eskandarian, Sam Kim, Maurice Shih ePrint Report An updatable encryption scheme is a symmetric-key encryption scheme that supports key-rotation on ciphertexts. A server that hosts a user's encrypted data can use a user-provided update token to rotate the key under which the data is encrypted while not learning any information about the underlying data. This work's contributions are threefold. First, we introduce new definitions for updatable encryption (in the ciphertext-dependent setting) that capture desirable security properties not covered in prior work. Next, we construct two new updatable encryption schemes. The first construction relies only on symmetric cryptographic primitives but only supports a bounded number of key rotations. The second supports a (nearly) unbounded number of updates and relies on almost key-homomorphic PRFs. We construct an efficient almost key-homomorphic PRF from the Ring Learning with Errors (RLWE) assumption to concretely instantiate our second construction. Finally, we implement both constructions and compare their performance to prior work. Our RLWE-based construction outperforms an existing updatable encryption scheme based on the hardness of DDH in elliptic-curve groups by over 200x in speed. Our construction based only on symmetric primitives has the highest encryption throughput, approaching the performance of AES, and the highest decryption throughput on ciphertexts that were re-encrypted fewer than fifty times, at which point the RLWE construction dominates. ###### Fabrice Benhamouda, Huijia Lin ePrint Report Reducing interaction in Multiparty Computation (MPC) is a highly desirable goal in cryptography. It is known that 2-round MPC can be based on the minimal assumption of 2-round Oblivious Transfer (OT) [Benhamouda and Lin, Garg and Srinivasan, EC 2018], and 1-round MPC is impossible in general. In this work, we propose a natural hybrid'' model, called \textbf{multiparty reusable Non-Interactive Secure Computation Market (mrNISC)}. In this model, parties publish encodings of their private inputs$x_i$at the beginning, once and for all. Later, any subset$I$of them can compute \emph{on-the-fly} a function$f$on their inputs$\vec x_I = {\{x_i\}}_{i \in I}$by just sending a single message to a stateless evaluator, conveying the result$f(\vec x_I)\$ and nothing else. Importantly, the input encodings can be \emph{reused} in any number of on-the-fly computations, and the same classical simulation security guaranteed by multi-round MPC, is achieved. In short, mrNISC has minimal yet tractable'' interaction pattern.

We initiate the study of mrNISC on several fronts. First, we formalize the security of mrNISC protocols in both a UC definition and a game-based definition. Second, we construct mrNISC protocols in the plain model with semi-honest and semi-malicious security based on bilinear groups. Third, we demonstrate the power of mrNISC by showing two applications: non-interactive MPC (NIMPC) with reusable setup and a distributed version of program obfuscation. In addition, at the core of our construction of mrNISC is a witness encryption scheme for a special language that verifies Non-Interactive Zero-Knowledge (NIZK) proofs of the validity of computations over committed values, which we believe is of independent interest.
###### Florian Tramèr, Dan Boneh, Kenneth G. Paterson
ePrint Report
Privacy-focused crypto-currencies, such as Zcash or Monero, aim to provide strong cryptographic guarantees for transaction confidentiality and unlinkability. In this paper, we describe side-channel attacks that let remote adversaries bypass these protections. We present a general class of timing side-channel and traffic-analysis attacks on receiver privacy. These attacks enable an active remote adversary to identify the (secret) payee of any transaction in Zcash or Monero. The attacks violate the privacy goals of these crypto- currencies by exploiting side-channel information leaked by the implementation of different system components. Specifically, we show that a remote party can link all transactions that send funds to a user, by measuring the response time of that user’s P2P node to certain requests. The timing differences are large enough that the attacks can be mounted remotely over a WAN. We responsibly disclosed the issues to the affected projects, and they have patched the vulnerabilities. We further study the impact of timing side-channels on the zero-knowledge proof systems used in these crypto-currencies. We observe that in Zcash’s implementation, the time to generate a zero-knowledge proof depends on secret transaction data, and in particular on the amount of transacted funds. Hence, an adversary capable of measuring proof generation time could break transaction confidentiality, despite the proof system’s zero-knowledge property. Our attacks highlight the dangers of side-channel leakage in anonymous crypto-currencies, and the need to systematically protect them against such attacks.
###### Michele Ciampi, Luisa Siniscalchi, Hendrik Waldner
ePrint Report
In this work, we provide a compiler that transforms a single-input functional encryption scheme for the class of polynomially bounded circuits into a multi-client functional encryption (MCFE) scheme for the class of separable functions. An n-input function f is called separable if it can be described as a list of polynomially bounded circuits f^1, ... , f^n s.t. f(x_1, ... , x_n)= f^1(x_1)+ ... + f^n(x_n) for all x_1 ,... , x_n.

Our compiler extends the works of Brakerski et al. [Eurocrypt 2016] and of Komargodski et al. [Eurocrypt 2017] in which a generic compiler is proposed to obtain multi-input functional encryption (MIFE) from single-input functional encryption. Our construction achieves the stronger notion of MCFE but for the less generic class of separable functions. Prior to our work, a long line of results has been proposed in the setting of MCFE for the inner-product functionality, which is a special case of a separable function.

We also propose a modified version of the notion of decentralized MCFE introduced by Chotard et al. [Asiacrypt 2018] that we call outsourceable mulit-client functional encryption (OMCFE). Intuitively, the notion of OMCFE makes it possible to distribute the load of the decryption procedure among at most n different entities, which will return decryption shares that can be combined (e.g., additively) thus obtaining the output of the computation. This notion is especially useful in the case of a very resource consuming decryption procedure, while the combine algorithm is non-time consuming. We also show how to extend the presented MCFE protocol to obtain an OMCFE scheme for the same functionality class.


text:
10,818 Pages

# Rgetar

My favorite wikis
• ## Ordinals array function

June 6, 2017 by Rgetar

I interested in ordinals, and I asked myself: "Why we use $$\omega$$,  $$\omega2$$, $$\omega^2$$, $$\omega^\omega$$, $$\epsilon_0$$, $$\zeta_0$$, $$\phi(3,0)$$, $$\Gamma_0$$ etc. instead of $$\omega\uparrow\uparrow\uparrow\omega$$, $$\omega\uparrow\uparrow\uparrow\uparrow\omega$$ etc.?"

But I realized this doesn't work beyond $$\epsilon_0$$ since $$\omega\uparrow\uparrow(\omega+1) = \omega^{\omega\uparrow\uparrow\omega} = \omega^{\epsilon_0} = \epsilon_0 = \omega\uparrow\uparrow\omega$$.

I experimented and created a BEAF-like system, suitable also for ordinals.

It is family of functions [X]a of ordinal a.

Let X - sequence of ordinals (or "negative ordinals", i.e. ordinals with "-" sign before them) with separators.

All zeros we may omit.

All lef…

format: plain


text:
Studﬁnder: Wire Edition

Craig Macomber, Milda Zizyte
June 10, 2011

# Introduction

Often, humans are faced with the problem of finding that which they cannot see. The five senses are limited and in particular do not extend to wavelengths outside the audible or visible spectrum. Auxillary devices employing sensing solutions are thus required to augment the senses.

Such sensing capabilities are conceivably very important. In the area of electric sensing, a person might want to locate power behind a wall or want to figure out the closest source of power in a busy room.

In particular, humans cannot easily locate electric fields. However, given sufficient hardware and clever filtering, it is possible to detect the 60 Hz electric fields emanating from wall outlets and the cables attached to them. [1] uses such a scheme, with a copper-coated electric plug face as one electrode and the ground prong of the plug as another, to scan for such fields and allow a robot to effectively “feed itself” by guiding itself to power.

In fact, the robot Marvin faces the same problem humans do - just as a robot cannot see these electric fields, neither can humans. Our project aims to provide human perception of such phenomena by hardware which translates an electric input into minimal visual feedback. We thus achieve the analog of an electric studfinder - a device which senses otherwise invisible objects (obscured by obstacles or otherwise) and conveys them with a few blinking lights. In fact, our solution provides enough information for a user to be aware of electric cables in the wall to prevent from drilling into them!

Our solution combines analog filtering with digital processing to achieve its goal. It is an easily adaptable and potentially portable device with many possible applications and implications.

# Analog Hardware Design

The analog circuit has three main purposes:

1. To receive and filter an input electrode current into a clear voltage output signal
2. To convey the output using minimal complexity
3. To effectively interface with an Arduino Uno for digital processing

(1) is the most complex, requiring filtering a current source. A MCP6024 quad op-amp package is used for this purpose, and is described in a later section.

(2) is accomplished by the use of three LEDs, denoted “left,” “right,” and “amplitude.” In this way, we can convey both direction and strength of the electric field by modulating brightness. This seems like the most natural and unobtrusive way of translating electric fields to a “human-readable format,” as it is less irksome than audio output and easier to implement, as well.

(3) strongly depends on (1) and (2). In particular, the Arduino places constraints on how many wires we can use and the form our outputs take. We opted two use two analog input pins post-filtering, and three pulse-width modulated pins for outputs into the LED.

An overview of our circuit is thus figure 1. EL and ER denote the left electrode signal and right electrode signal, respectively.

## Electrodes

Our electrodes, or antenna, are simple in design. Due to the low operating frequency, there are no real restrictions on what shapes pick up a strong signal. Our design needed to meet two requirements: producing a sufficient signal, and providing a directional differential signal. With our antenna's two electrodes are simple copper tape rectangles. The length of the tape, which sets the height of our antenna determines the signal strength, and the separation sets the directional sensitivity. A good balance of both is required to be able to both detect a signal from a significant distance, as well as to tell what direction it is coming from. Our final shape was mostly determined by supply available, and some guessing about how much signal we needed based on our original smaller electrodes. Our final measurements are 300 mm across, 240 mm high. The makes the electrodes 25 mm by 240 mm with a separation of 240 mm (265 mm center to center).

Also, the symmetry is very important: both electrodes are the same area. Otherwise, our differential zero point would be off.

We chose acrylic to mount the copper tape on for three main reasons:

1. It is a good insulator. The plastic used is scrap from an old electrostatics project and was originally selected for its insulating properties. If the substrate for our antenna were a conductor, our two electrodes would be connected, and we would lose the directional signal.
2. It is transparent. This makes it much easier to see what one is doing when using it near the source its detecting, as is the case when following wires in walls.
3. We had some available. There are plenty of other materials that would have also worked well, but we simply chose the one we had in the correct size.

## Filtering

The circuit shown here provides a current to voltage conversion, followed by a low pass filter tuned to easily pass anything near 60 Hz or lower. Since there is vastly more 60 Hz signal than any nearby or lower frequency, a sharp cutoff was not needed.

Notice that our cutoff frequency is:

(1)
\begin{align} f = \frac{1}{2\pi (100 k\Omega)(.01\mu F)} = 159 Hz. \end{align}

Our original filter had a resistor value of twice that for an 80 Hz cutoff. Experimentation yielded less than satisfactory results, so we decreased our resistor value. This still cuts off most high frequency noise, as we are mostly worried about noise in the kilohertz and above.

We went for a simple active filter along with some additional gain. This design allowed all the needed analog filtering using only two op-amps per channel. Thus, we only needed four op-amps total, one package.

The transimpedance stage, which converts the electrode's current signal to a voltage signal uses a 2M resistor. Some experiments were run on what values worked best.

The second stage, an inverting low pass amplifier with a cutoff frequency of 160 Hz and a gain of 50. This removes high frequency noise, and brings our signal up to an accurately measurable size.

## Output

We opted for a simple output of three LEDs. Two of them are directional and almost directly correspond to each component of the antenna. The third is a magnitude antenna, which helps the user distinguish how strong the observed signal is. No analog magic is used for this part of the circuit: there are just the conventional resistors to ground, and everything else is driven by digital logic, discussed in the next section.

Pulse-Width Modulated pins were used for the LEDs so that we could control their brightness using the Arduino.

Throughout the development and testing process, we tried a few different display approaches. Initially we simply had one output, which when low, lit one light, and when high lit the other. Initially this was a digital output, simply high or low. When the antenna was pointed at the field source, both lights would flicker and it would be confusing. We then converted to using pulse width modulated outputs. This helped, but we found both lights coming on to be not very useful, which lead to the final design. Only one light is on at once, and the brightness depends on the amount that the antenna needs to turn. To make out full level of sensitivity apparent, we multiplied up the signal so the LEDs saturate pretty early, and its easy to see small angular differences.

# Firmware

The comments explain the code in detail. At a high level it reads in the two signals, and uses an IIR filter to computer the mean. It then subtracts the mean from the signals removing the DC offset. Finally the signals are rectified and smoothed with another IIR. It then takes the difference of the absolute magnitudes to get direction, and output that to the left and right LEDs. We also apply an IIR to our magnitude LED to smooth out flicker.

We experimented with several values for both $a$ and $b$ in our code. As the purpose of the LEDs is to convey first-nature, intuitive information about what the antenna senses, this experimentation was not precise. We noticed a trade-off between “flicker” (how much and how often the signal changed in a distracting fashion) and speed (how quickly the LEDs mimicked the action of changing the configuration of the antenna) and settled on some values that generally worked well. Depending on use case, these values may need to be readjusted.

// These constants won't change.  They're used to give names
// to the pins used:
const int left = A0;     // Analog input pin for the left electrode
const int right = A1;    // Analog input pin for the right electrode
const int leftLED = 11;  // PWM pin for the left LED
const int rightLED = 10; // PWM pin for the right LED
const int ampLED = 9;    // PWM pin for the amplitude LED

const float a = .2;      // filter value for the left/right IIR low-pass filter
const float b = .008;    // filter value for the output IIR low-pass filter (for smoothing)

// used for IIR
static float leftmid = 0;
static float rightmid = 0;

float signal = 0; // difference of the filtered left/right signals

// used for IIR
static float signalLeft = 0;
static float signalRight = 0;

// writing to serial at intervals
int count = 0;

void setup() {
// initialize serial communications at 9600 bps:
Serial.begin(9600);

// initialize pins:
pinMode(left, INPUT);
pinMode(right, INPUT);
pinMode(leftLED, OUTPUT);
pinMode(rightLED, OUTPUT);
pinMode(ampLED,OUTPUT);
}

void loop() {

// Apply an IIR to each one
leftmid  = a*l + (1-a)*leftmid;
rightmid = a*r + (1-a)*rightmid;

// Take the magnitude without the DC components
float left = abs(l-leftmid);
float right = abs(r-rightmid);

// Smooth them out with another IIR
signalLeft = left * b + (1-b)*signalLeft;
signalRight = right * b + (1-b)*signalRight;

// Take the difference (negative signal means more input on the right; positive means more on the right)
signal = (signalLeft - signalRight);

// duty factor for amplitude output: just the sum of the amplitudes we've seen
int df = min(255,(int) (signalLeft+signalRight));
analogWrite(ampLED,df);

// Output to the LEDs: the *32 is to favor a large signal in one of the LEDs, but if the signal is in the middle, both LEDs are going to be dimmer
analogWrite(leftLED,min(255,max(0,signal*32)));
analogWrite(rightLED,min(255,max(0,signal*-32)));

// Print what we see to the monitor for data collection
if(count == 0) {
Serial.println(signal);
}

count = (count+1)\%100;
}

# Characterization

We performed several experiments and measurements to evaluate our circuit. They are as follows:

## Noise measurement

For this experiment, we simply held the antenna away from any visible powerlines in the middle of an isolated area. We took 234 samples from the arduino serial input with the antenna tilted both ways. Our results are outlined in table one (the output is the filtered analog $signal$ value as seen in the code above):

Average Standard deviation -0.08 0.138 -0.18 0.120

Since two positions were identical except mirrored swapping the electrodes, the bias can be computed as the difference of the two means. These results show little bias in the inputs, only 0.10. If desired, this could be reduced by some calibration. Calibrating out the bias would require two adjustments. The first to remove the zero signal offset measured here, and a second to scale the data to compensate for multiplicative errors.

The noise was of a comparable scale to the bias, also very small.

## Signal to Noise Ratio

We also took samples of a strong signal (the antenna close to a power outlet with a cord in the wall, which was our strongest pick up) and measured the mean and standard deviation: the mean turned out to be 163.86, and the standard deviation 2.43. This leads to a signal-to-noise-ratio of

(2)
\begin{align} SNR = \frac{163.86}{2.43} = 67.432 \end{align}

Unfortunately, looking at the details for this data, it seems likely that some of the signal was clipping, so it is not an accurate measurement.

Using some of our other data from the antenna in a strong field, 30 cm from an extension cord, we computed this:

(3)
\begin{align} SNR = \frac{2.165}{0.0872} = 24.828 \end{align}

This includes the variations from not holding the antenna still, and is still quite good. Since our data used here was with the antenna oriented to produce low differential signal, the signal value is taken from the same position, but with a different orientation to measure the actual field present. Using the sum for this would have been better. Further data collection to measure the SNR under more conditions would provide more detail, but currently we do not have such data.

This high signal to noise ratio was achieved by averaging over a long period with our IIR filter. It comes at the cost of somewhat slow response times, however for our uses, the response was plenty fast.

## Rotations

We performed several experiments with rotating the antenna with a fixed centerpoint, including the following:

 30cm from wall, bare socket rotation
 30cm from wall, cord in wall rotation
 1.5m from wall, bare socket rotation
 1.5 from wall, cord in wall rotation

These were all rotated by hand, which is not easy to do accurately. Even the strong and clean signals show some distortion, and the non-uniform rotation speed is probably part of the cause. Also, in some of the tests, rotation started a little way into data collection leaving a flat spot at the beginning. With this taken into account the graphs all resemble a sine waves of various amplitudes with varying clarity.

If we assume the field is a uniform linear gradient with no curl (which is somewhat close to reality when far away from the source), an ideal version of our sensor would produce a sine wave. Thus, the sine wave was the expected result. The zero crossing show where the antenna's normal is inline with the field gradient (meaning its pointed at or away from the source), and the peaks show where the antenna is inline with the field gradient (the field source is in the plane of the antenna).

Even the weak signal from the wall socket alone (which was partly shielded by a metal face plate) still produced a sign wave in our 1.5 m test. This shows that we can still detect the direction of a socket from 1.5 meters away. The direction might not be too accurate, but it should be good enough to get closer where a more accurate signal would be available.

## Distance Variation

Another experiment was keeping the antenna in the same orientation parallel to some walls in a hall and moving it away from a visible socket, recording the data. We plotted the results as follows:

 Moving from 0 to 1.5m away from bare socket at steady pace
 Amplitude moving from 0 to 2m away from cord in wall at steady pace

These plots show 2 types of saturation related failures. The first shows that even if there is a strong differential signal, it can fail to be detected if both channels start clipping. At the beginning, we suspect the signal is so strong that the difference partly hidden by this effect. This however only seemed to be an issue in the most extreme case of the antenna sideways and up against the outlet.

The second plot shows the total sum amplitude, not difference. It shows the clipping, and a sharp falloff with distance. Since it is measuring the derivative of the electric field which falls off with the square of the distance, the signal is expected to drop off with the cube of the distance. While we can not accurately tell the shape of the curve, it looks like it is not clipping it may be roughly the expected proportional to $\frac{1}{d^3}$ where $d$ is the distance from the source.

# Conclusion

After looking at our LEDs, as well as some numeric data, we discovered a few things about our design. One is that we can get some clipping issues. This was not apparent from just looking at the LEDs, but perhaps we could get better signals for close/strong sources if we resolved the issue. Once approach would be logarithmic gain. Initially we avoided this because it added complexity, and we feared its reduction in differential signal might be an issue.

The other main thing we noticed from our numeric data was that we could tell the general direction from further away than was obvious from just our LEDs. One thing we could do to better display this so to lower the time constant on our final IIR filters for more smoothing and slower response. This would allow even the noisy long range signals to be directly usable as long as you don't turn too fast.

This relates to another change that would improve the usability across varying distances: using different tuning, and even antennas, at different distances/signal strengths. It would be possible to adjust time constants based on signal strength, and to shift over to higher precision antennas. This would also resolve most saturation issues if done correctly.

Another change we would make if redoing or continuing this project is to insulate the electrodes. Covering them with packing tape for example would help protect them from getting shorted to things accidentally, and should have little to no effect of the signal. Additional static protection for the first op-amp might also be a good idea.

While we have several ideas how the system could be improved, it does work quite well, and exceeded our expectations. It is able to do the two things that interested us: seeing through walls to follow and locate wires, and to detect outlets from long distances, up to and perhaps exceeding 1.5 meters.

The first of these uses is the most simple application. Now that good constants are known, it would be quite straightforward to produce a low power and low cost pure analog version. This could be mounted on the back of the antenna on the top out of the way. Then the directional LEDs could be wired out to near the electrodes for easy viewing, and a handle could be attached for easy gripping and pointing. If desired, such a system could include swappable (or multiple) antennas of differing sizes depending on the task, and perhaps some jumpers or switches on the board to rescale some of the constant adapt it for different use cases (long time constants and high gain for weak signals, vs low gain and fast responses for quick scans). It could even make a viable consumer product for locating wires to aide in wiring, or safety when drilling into walls.

The second use is detection of outlets for a robot. With the assumption that most outlets are at roughly the same height, our antenna could simply be placed on the front of a robot and would provide a signal for if there was a power source nearby (potentially and outlet, but perhaps a cord, or wire inside a wall). It would also provide a directional signal, which based on our data would be enough to steer the robot toward the outlet from 1.5 meters away, gaining accuracy as it got close. While our antenna might not be good enough to do the centering to plugin, as discussed above, it could be combined with a higher precision antenna, especially one that also has a vertical channel. Plugging into an outlet thats right in-front of the robot is one thing, but noticing one from the middle of the hall as our system can, and then going over to it and plugging in is a much more useful accomplishment if one is trying to make a robot that can recharge itself at outlets. There is a important detail with this however: its important that the robot does not produce a significant 60 Hz signal of its own. While this could potentially be calibrated out if its consistent, it would likely decrease sensitivity.

One interesting idea we have not had time to explore is whether it is practical to make a system that detects distances to the signal sources. Using signal strength is not enough because the signal emitting from the sources varies from source to source. Some sort of three electrode antenna could either detect the curve of the field, or its non-linear fall off depending on the placements of the electrodes. Either of these measurements could be used to compute the distance assuming something about the source shape (probably assume a point source). This, if it worked, would allow detecting the distances, which when combined with our existing approaches would allow a measure of location, distance, and using the amplitudes, the actual strength of the signal emitted from the source. With a bit of math, and assuming the signal source is in line with the two electrodes, it should be possible to compute a distance to a point source.

$k$=produced signal strength from source (unknown)
$x$=distance from near electrode to source (unknown)
$a$=measured signal at close electrode
$b$=measured signal at far electrode
$s$=distance between electrodes

(4)
\begin{align} \frac{k}{x^2}=a \end{align}
(5)
\begin{align} \frac{k}{(x+s)^2}=b \end{align}
(6)
$$k=a*x^2$$
(7)
\begin{align} \frac{s*\sqrt{\frac{b}{a}}}{1-\sqrt{\frac{b}{a}}}=x \end{align}

Eq.(7) provides the distance to a point source using a two electrode antenna, which can be used in Eq.(6) to get the strength of the point source. We never had a chance to apply this, and it would be interesting to see if it produced usable results. These equations are derived from Eq.(4) and Eq.(5) which simply represent the electric field falling of with the inverse square law.

The real limit of sensing the field is to have a lot of antennas. With enough knowledge of the local electric field, it should be theoretically possible to reconstruct the field outside the of the local area and locate multiple sources. As the number of antennas grows, interference from them may become an issue, which could be countered with having fewer moving antennas, or smaller ones with more gain. What we don't know is how far in this direction it is practical to go. Clearly one and two antenna designs work and produce useful results, but how much can be gained from extending this remains a topic for further study.

# Video

Bibliography
1. Brian Mayton, Louis LeGrand, Joshua R. Smith.
Robot, Feed Thyself: Plugging In to Unmodified Electrical Outlets by Sensing Emitted AC Electric Fields. Proceedings of the 2010 IEEE International Conference on Robotics and Automation (ICRA 2010)


text:
Problems

 OWY 1.26b Is the discrete-time signal $x[n] = \cos \left(\frac{n}{8}\right)$ periodic? If it is, what is the time period? OWY 1.26c Is the discrete-time signal $x[n] = \cos \left(\frac{\pi n^2}{8}\right)$ periodic? If it is, what is the time period?

 OWN 2.6 Compute the convolution of $x[n] = \left(\frac{1}{3} \right)^{-n} \ u[-n-1]$ and $h[n] = u[-n-1]$

 Consider the system defined by $y(t) = x(t) \ u(t)$. Is this linear, time invariant, stable, invertible?

Bandpassfromoldexam
DTFS
Phasefunction
Two systems
Problem5fromoldexam - There is a small mistake in the solutions to the last part. The correct answer is 450Hz,500Hz,550 Hz

page revision: 22, last edited: 15 Nov 2017 04:52
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License


text:
# Using Principal Components to create my y variable when many different y variables are available

I have a set of LHS variables ($$y_{1i},y_{2i},...y_{ki})$$ where $$i=1..N$$ represents observations, and $$j=1...k$$ represent different possible $$y$$ variables. These variables are highly correlated- think of them as different measures of economic activity, such as GDP, GNP, Gross National Income, Domestic Absorption. etc. While each of them is interesting in its own right, theory tells me to use some measure of economic activity, in a regression of the form: $$y=\boldsymbol{x}\beta+\epsilon$$ where $$\boldsymbol{x}$$ represents the same set of explanatory variables. It is therefore not clear which of these measures to use in my regression. I could run individual regressions for each of the different $$y$$ and compare results, but that would essentially be a form of p-hacking, where I could choose which measure produces most significant coefficients, for instance. I could take an average of each, such that for any observation $$i,$$ I would construct:~ $$\bar{y}_{i}=\frac{1}{K}\sum y_{ik}$$ The problem with this is that I would be weighing each of these measures equally, and there is no reason to think why that would be correct. Another thought I had was to use Principal components, and construct for instance, the first principal component of each of these $$y$$ variables. This would be a variance-maximizing weighted average of the different $$y,$$ which is less ad-hoc than a simple average. My question then is this: is it OK to use PCA to construct a dependent variable when several similar dependent variables are available?


text:
## WordPress wp-latex plugin without dvipng

I wanted to install the excellent wp-latex plugin for WordPress, which allows the inclusion of LaTeX equations in posts and comments but my ISP did not have dvipng installed, one of its prerequisites, nor some libraries I would need to build my own copy there. I patched the plugin to instead use dvips and convert, which are both part of the standard LaTeX distribution. If anyone in a similar situation needs the plugin and the author doesn’t accept my patch into the official version, you can contact me for it. The patch is only a few lines. [Update: The author has accepted the patch. Until version 1.0 is released you can get the latest svn version.] Most people who have or can get LaTex on their web server should be able to get dvipng installed (and I expect that my ISP will respond to my request to install it), and dvipng is probably a bit faster, but the patch is an alternative for those who need it.

As an example of what wp-latex can do, here is the equation for the protein translation component of my simulation, part of the formula for protein rate of production, not including terms for death and diffusion.

$\sum_{i=1}^{N_{G}} \sum_{l=1}^{N_{P}} \prod_{k=1}^{N} p_{l} g_{i} f^{\prime}_{\mathit{RES}}(R(x))\xi_{ikl}^{(1)}f(l,c_{ik},a_{jk})$

Much thanks to John Hedditch who worked out the equations and translated them into a numerical simulation during a couple of intense days of collaboration we had at his office in Brisbane recently.

I’ve upgraded WordPress to version 1.5.1. It was as easy as the installation instructions make it out to be. The only extra step was running my script that sets all the file permissions for secure PHP operation, as described in Securing PHP applications at Sonic.net.

This new version includes the fix for the problem with sending email when running in safe mode.

Coincidentally, my web hosting ISP, sonic.net, has turned off safe mode in their PHP installation, making all the safe mode workarounds I’ve been blogging about no longer necessary. Life has become simpler.

## Safe mode and WordPress registration mail

WordPress failed to send email, such as when registering a name or trying to retrieve a password. The problem turned out to be in the wp_mail function in wp-includes/functions.php.

It takes an optional argument $more, which it passes on to mail() as its fifth argument. The php mail() function is documented not to accept that fifth argument when in safe mode. The fix is to call mail() without that$more argument either when in safe mode and/or when $more == ”. I have since found that this change is already in the development source of WordPress. See changesets 2365 and 2415. [Update, May 12, 2005] WordPress 1.5.1 has been released and contains the fix to this problem. ## [DokuWiki | blikithoughts] This post is an experiment with the WordPress dwBliki plugin and a rambling about blog/wiki integration in general. Even though the title and categories make it look like one of the DokuWiki entries, I’m creating it in WordPress. I’ve seen that the plugin will take a new DokuWiki page and put it in the WordPress blog. Now let’s see if works in reverse to put this in the DokuWiki. If it does, that will be be pretty cool. If it doesn’t I’ll see what happens if I then create a page with this name in the DokuWiki. So, what does it mean to integrate a blog and a wiki? The dwBliki plugin seems to ignore that question in favor of simply implementing the cool hack of embedding the full blown DokuWiki inside a WordPress plugin so that wiki pages become blog entries. The difficulties I’m seeing with that have to do with the mismatch of purposes. A blog consists of a series of frozen snapshots ordered by time. A blog grows in two directions, through the addition of new posts and through the comments and trackbacks. Editing old posts undermines the blog by rewriting history without informing interested past readers. A blog is the creation of an individual. It is a personal journal, or at least a vehicle for the creative work of a particular author or a small collaboration of authors. Even when a blog is used as a discussion forum, posts are the creation of a blog owner, replies are the static creations of their authors linked in a temporal chain. A wiki consists of a web of linked expressions of topics. The expressions and the links change over time. There is no “author” for a page. Even though it is possible to follow the revisions of a page and see who the authors were, a wiki does not provide a view that would make that history visible as a form of discussion thread. So what does it mean to combine a blog and a wiki? I have some ideas about that, but I’m going to save it for a later post. Right now I want to see the results of the experiment and get some sleep. [update:] I created a page in the wiki named blikithoughts, which would have created a blog entry with this name. This blog page did not change. ## Theme Switcher Shim plugin Here’s a plugin that lets the themes in the Theme Contest repository work with the Theme Switcher plugin you find in Plugin Manager. This is really confusing. The WP Plugin Manager refers to a central database of plugins. It has a Theme Switcher Plugin. To use it you add a call to get_theme_switcher() in sidebar.php where you want the list of themes to appear. If you have Plugin Manager installed, with one click you can install or update Theme Switcher. Then all you need to do is edit every one of the themes you download to put the correct snippet of code in sidebar.php. The WP Themes contest that I’ve mentioned before refers to a different Theme Switcher plugin. It works pretty much the same way, except it uses a different name for the function to be called from sidebar.php. If you install that Theme Switcher plugin, then all you do is download the themes from the contest site. They all have the correct code in their sidebar.php to work with this Theme Switcher. Oops. That isn’t the Theme Switcher you get when you update in Plugin Manager. The solution: Theme Switcher Shim, a plugin that I am submitting to the WP Plugin Manager database. If you have WP Plugin Manager, you can get it with a one click install. There is no configuration involved in using it. When you have Theme Switcher plugin installed from Plugin Manager, then Theme Switcher Shim will just work. If you don’t have the Theme Switcher plugin installed, the shim detects that and does nothing. You can install Theme Switcher Shim manually by unzipping theme-switcher-plugin.php into your wp-contents/plugins/ directory, but it doesn’t make a whole lot of sense to do so: Its usefulness is in regards to WP Plugin Manager and the one-click install. ## Installing Spell Checker plugin in safe mode I’m trying to add the Spelling Checker Plugin. It doesn’t work in safe_mode. I’m trying to change that. Let’s see if this can be spell-checked and posted. Yes, it works!! Here is a summary of the changes I made to the original code version Beta 1.17 14-March-2005. I hope the author of the plugin will be able to make this post obsolete by folding the changes into his plugin. First, the conditions under which this was tested: My hosting ISP provides PHP running in safe mode with safe_mode_exec_dir set to “.” and PHP built –with-pspell. That means that aspell is installed on the server. It is in/usr/bin/aspell. I installed WordPress using PHP built as a cgi and called with CGIWrap using the techniques described in Securing PHP applications at Sonic.net. That may have affected which directory is “.” at time of the call, and therefore which directory I had to install the shell script named aspell that acts as a shim for the call to the system aspell. This will only work for you if safe_mode_exec points somewhere that you can put your own shell script. 1. Disable the test in spellcheck-plugin.php that blocks installation when running in safe mode. 2. Bypass the exec(“which aspell”) call, which will not work in safe mode. Instead set the result variable of the call to be “aspell”. The location of the aspell command on the server is not relevant because safe mode restricts execution to files in the safe_mode_exec_dir directory. 3. Create a shell script wp-contents/spell-plugin/aspell that is set to be executable and contains  #!/bin/sh /bin/sh -c "/usr/bin/aspell$*" 2>&1
This can’t be a simple softlink because of the way that safe mode escapes the redirection in the command line.
4. Replace the two calls to shell_exec() with calls to exec(). In the one place that uses the return string from shell_exec use the second argument to exec and the join function to get the same result.

Here are the diffs for the code changes I made:
 diff -r ~/spell-plugin/spell-plugin.php ./wp-content/plugins/spell-plugin.php 169c169 < if(ini_get('safe_mode')) --- > if(ini_get('xxxsafe_modexxx')) 260c260 < exec( "which aspell 2>&1", $out,$err ); --- > $out[0] = "aspell";$err = 0; diff -r ~/spell-plugin/spellInclude.php ./wp-content/spell-plugin/spellInclude.php 114c114 < shell_exec( $cmd ); --- > exec($cmd ); diff -r ~/spell-plugin/spellchecker.php ./wp-content/spell-plugin/spellchecker.php 95c95,97 < if( $aspellret = shell_exec($cmd )) { --- > exec( $cmd,$execout ); > $aspellret = join("\n",$execout); > if( \$aspellret ) {

## Installing Plugin Manager in safe mode

This was almost too easy!

The problem: Plugin Manager uses exec() to call the unzip command to extract files from plugin archives. This does not work in safe mode. On my hosting ISP, PHP is run in safe mode with safe_exec_dir set to “.”, which restricts exec() to calling only executables in the current directory.

The solution: Create a symbolic link for unzip in the main WordPress directory, pointing to /usr/bin/unzip

My hosting site has allow_url_fopen set, so I did not have to work around a similar call to wget that Plugin Manager uses in the absence of allow_url_fopen.


text:
# Complexity of Homogenizing a String

Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of integers to the other. We were able to reduce that problem to the following very natural problem that seems to have connections to edit distance, grouping by swapping, and minimum common string partition.

Problem: We are given a string, i.e., a sequence of letters, and our goal is to homogenize it at minimum cost. That is, we want a rearranged sequence such that all letters that are alike are next to each other.

The only operation that is permitted is to pick up a subsequence of letters that are alike, and move that subsequence anywhere, and that costs me 1 unit.

Any help characterizing the complexity of this problem would be much appreciated!

Example:

• a a b c d a b: Input
• b c d a a a b: After moving the first a a to the position right after "d"
• b b c d a a a: After moving the trailing b to the first position

Since the resulting string is homogeneous, we have a cost of 2.

Note that we are not constrained in any way with respect to the output: as long as it is homogeneous, we don't need to ensure any specific order.

This problem is NP-complete, by reduction from Minimum Hitting Set.

In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$.

The reduction is as follows:

• The string is as follows: For each element $u \in U$, there will be a two characters of the string, $u'$. Between these characters will a character $s'$ for each $s \in S$ such that $u \in s$. Between the pairs of $u'$s, there will be unique characters that are not repeated in the string.

• To homogenize the string, the $s'$ character must be moved $|s|-1$ times, for each $s$. Additionally, for each $u$, the $u'$ character must be moved once, unless every $s'$ between the pair of $u'$ has been moved elsewhere.

• Therefore, to minimize the number of moves necessary to homogenize the string, we wish to maximize the number of $u'$ such that every $s'$ has been moved elsewhere. The $u'$s where the $s'$s have not been moved elsewhere must together contain a $s'$ for every $s \in S$, so they must for a hitting set. Moreover, any such hitting set may serve as the ending locations of the $s'$s, by moving each $s$ to the $u$ which hits it.

• Thus, the number of moves to homogenize this string is equal to $\sum |s| + |H^*|$, where $H^*$ is the minimum hitting set.

Since minimum hitting set is NP-Hard, optimally homogenizing a string is as well. Since the moves form a witness, it is NP-Complete.

• This is an elegant reduction -- thank you! – Aditya Parameswaran Jul 3 '17 at 15:29

Look at the number of changes from one letter to the other in your string, which you could see as a measure for the string's inhomogenity. With every (useful) move of a subsequence you reduce this number by one if the subsequence you move is preceded and followed by two distinct letters. Otherwise you reduce the inhomogenity by two.

So for a string with k changes you need at most k - l + 1 moves where l is the number of different letters in the string, because in the end l - 1 changes will remain. As a string of length n can have at most n-1 letter changes, it can need at most n - l moves. The least possible number is half of this.

The best strategy seems thus to look for subsequences of the form abbba and to move the bbb away from there. When there are none left, move whatever. You could still try to do those operations that create new abbba situations, but I think the gain will be very little. Since the worst possible strategy (without silly moves that increase the inhomogenity) uses at most twice as many moves as the optimal one, the little you might gain seems to be in no reasonable relation to the effort as the answer by isaacg with the characterization as NP-hard suggests. Unless, of course, you really only count the number of move operations and do not care about the time to decide which moves to make.

The worst case is therefore a string where every letter is different from its predecessor (and you do not get any abbba bonuses). Here you need a number of operations linear in the length of the string and almost equal to this length.

In your example, you have 5 -> 4 -> 3 changes, and 3 equals the number of letters (4) minus 1.

Side note: For an alphabet of size only two, every move that does not move a prefix or suffix of the string reduces the inhomogenity by two and thus every sequence of reasonable moves is optimal.

• You claim that a move can reduce the number of changes by at most 2, but actually it can reduce the number of changes by up to 3. For example, converting "aabcabc" to "aaabbcc" by moving the first substring "bc" into the middle of the second substring "bc" results in a decrease of the number of changes in the string from 5 to 2. – Mikhail Rudoy Jul 1 '17 at 6:39
• Hi, @MikhailRudoy. The questions states that the operation is "pick up a subsequence of letters that are alike", so bc is not allowed as far as I understand. – Peter Leupold Jul 1 '17 at 10:56
• I completely missed that detail. You are correct in that case. – Mikhail Rudoy Jul 2 '17 at 5:20
• Peter is correct: those moves are not permitted. – Aditya Parameswaran Jul 3 '17 at 15:33
• Re: the rest of the answer -- indeed, these observations re: lower-bounds, optimality of the alphabet size 2 case, and heuristics for what to do at any point are valuable. Since any move in the worst case only benefits that sequence of letters, and in the best case merges at most two sequences of letters like in your abbba, a 2-approximation seems natural. – Aditya Parameswaran Jul 3 '17 at 15:39


text:
# Finding motifs: fasta file with 10,000 sequences

I am new to Python. I am trying to parse a fasta file containing 10,000 sequences to look for motifs (microsatellites in particular). I tried using Seq Utils to parse my sequences for a particular motif, that is, (TG)20. I suspect because I used the string function (str), it treated the entire fasta file as a one single fasta sequence. I then tried using BruteForce on the motif (TG)17 and found that an error appeared which said that "...the object of type 'FastaIterator' has no len()...". The script however worked when only a single sequence was in the fasta file.

In essence, I need some help figuring out how to:

• Prepare an instances object(is this correct?) with microsatellite motifs (for starters, I intend to parse the sequences for dinucleotide repeats (TG)10,(AC)10,(AT)10 and (AG)10;
• Parse my 10,000 long sequence file using this object(?); and
• Print an output specifying which of my sequences contain microsatellite motifs.

Appreciate any help I can get on this.

#Seq Utils to find Motifs

>>> pattern = Seq("TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG")
>>> sequence = Seq(a)
>>> results = SeqUtils.nt_search(str(a),pattern)
>>> print(results)
['TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG', 38, 40, 42, 44, 46, 48, 50, 52, 54,
56, 58, 68682, 68684, 68686, 370986, 370988, 370990, 370992, 370994, 370996, 43
8620, 438622, 438624, 438626, 438628, 438630, 438632, 438634, 438636, 438638, 43
8640, 556703, 556705, 556707, 784973, 784.... # it's too long so I am just pasting the first few lines

#BrutForce to find Motifs in a fasta file containing 10,000 sequences

>>> def BruteForce(s, t):
...     occurrences = []
...     for i in range(len(s)-len(t)+1):
...         match = True
...         for j in range(len(t)):
...             if s[i+j] != t[j]:
...                 match = False
...                 break
...         if match:
...             occurrences.append(i)
...
...     print(occurrences)
...
...

>>> t = "TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG"
>>> len(t)
34
>>> s = SeqIO.parse("group23.fas", "fasta")

>>> BruteForce(s,t)
Traceback (most recent call last):
File "<console>", line 1, in <module>
File "<console>", line 3, in BruteForce
TypeError: object of type 'FastaIterator' has no len()

#BrutForce to find Motifs in a fasta file containing a single sequence

>>> s = SeqIO.read("group23v.fas", "fasta")
>>> BruteForce(s,t)
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 79, 98, 117, 175, 193, 198, 217, 221, 277, 279, 282, 289, 294, 304, 311, 335, 381, 437, 464, 468, 510, 514, 522, 593, 602, 622, 634, 647, 658, 678, 704, 727, 750, 773, 804, 889, 895, 908, 911, 922, 937, 969, 975, 978, 1002]

Bio.SeqIO.parse() returns a SeqRecord iterator. To access the sequence of this sequence record, you need to use the .seq attribute so you should update your s with s.seq.

To expand on haci's answer (and since you mentioned being new to Python) you can loop over the iterator object and use the seq attribute like this:

pattern = Seq("TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG")
for record in SeqIO.parse("group23.fas", "fasta"):
results = SeqUtils.nt_search(str(record.seq), pattern)
print(results)

(More info on iterators here.) That will work the same whatever the number of sequences in group23.fas.

I'd be cautious about looking for microsatellites with fixed strings. If the sequences you're looking for are short and have imperfections among the repeats, you might miss them, depending on how many perfect repeats your search pattern has. For example with these stub example sequences:

>seq1
TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG
>seq2
ACGATGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG
>seq3
TGTGTGTGTGTGTGTGTGTGTCTGTGTGTGTGTGTGTGTG

The nt_search output gives you:

['TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG', 0]
['TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG', 4]
['TGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTGTG']

That is, one match at position 0 of the first sequence, one at position 4 of the second, and no matches for the third (there's a C I put in the middle). This might not be relevant for you if you're looking microsatellites much longer than your search patterns, but for shorter ones it might be a problem.

• Hi Jesse and @Haci. Thanks so much! I followed both your advice and it worked. I tried something less common, that is, trinucleotide repeats (AGC)10 i.e. pattern=Seq('AGCAGCAGCAGCAGCAGCAGCAGCAGCAGC') I used the following script >>> for record in SeqIO.parse("group23.fas", "fasta"): ... results = SeqUtils.nt_search(str(record.seq), pattern) ... print(results) ... print(record.id) The nt_search output gave the following! (only showing two examples): NODE_226753_..cov_2.031008 ['AGC...'] NODE_226754_..._cov_2.021041 ['AGC...', 265, 268, 271, 274] Oct 9 '20 at 1:42

Here's a solution that I came up with after help from both haci and Jesse. It involves using the following modules: os, glob, SeqIO, Seq, SeqUtils.

import os, glob

os.chdir("C:\python38\Lib\site-packages\Bio\SeqIO")

from Bio import SeqIO

from Bio.Seq import Seq

from Bio import SeqUtils

patttern = Seq("ACACACACACACACACACAC")

folder_path = 'C:\python38\Lib\site-packages\Bio\SeqIO' #specified the folder where my sequences were stored

fasta_paths = glob.glob(os.path.join(folder_path, '*.fasta')) #glob module finds all the pathnames matching a specified pattern i.e. '*.fasta'

with open("motif4.txt", "w") as f:
... for fasta_path in fasta_paths:
...     print(fasta_paths)
...     for seq_record in SeqIO.parse(fasta_path, "fasta"):
...         results = SeqUtils.nt_search(str(seq_record.seq),pattern)
...         f.write(str(results)) #replace with seq_record.seq to save the list of node names of all sequences that were parsed
...         f.write("\n") #ensures results of the parse through all the sequences in the fasta_path is written to a new line
... f.close()

The nt_search output gave the following output (similar to what Jesse showed):

1 ['ACACACACACACACACACAC']
2 ['ACACACACACACACACACAC']
3 ['ACACACACACACACACACAC']
4 ['ACACACACACACACACACAC']
5 ['ACACACACACACACACACAC']
6 ['ACACACACACACACACACAC', 16636, 16638, 16640, 16642, 16644, 16646, 16648, 16650, 16652, 16654, 16656, 16658, 16660, 16662, 16664]
7 ['ACACACACACACACACACAC']
8 ['ACACACACACACACACACAC']
9 ['ACACACACACACACACACAC']
10 ['ACACACACACACACACACAC']
11 ['ACACACACACACACACACAC', 9174]

It would miss sequences that did not match (AC)10 or those with imperfect repeat motifs. However, in cases where the motif was > (AC)10, nt_search listed down all locations where the motif was found sequentially. For example, in line 6, all locations were listed and showed the motif was in fact 36 nucleotides long in total (pos #16,636 to #16,673).

You can then import the txt. files into a databasing app and analyse the results.


text:
Integrating velocity equation to find position?

1. Oct 5, 2011

Cryptologica

1. The problem statement, all variables and given/known data

For t < 0, an object of mass m experiences no force and moves in the positive x direction with a constant speed vi. Beginning at t = 0, when the object passes position x = 0, it experiences a net resistive force proportional to the square of its speed: Fnet = −mkv2, where k is a constant. The speed of the object after t = 0 is given by
v = vi/(1 + kvit).

(a) Find the position x of the object as a function of time. (Use the following as necessary: k, m, t, and vi.)

(b) Find the object's velocity as a function of position. (Use the following as necessary: k, m, t, vi, and x.)

2. Relevant equations

a = Δv/Δt
v = Δx/Δt

3. The attempt at a solution

I am suspecting that I need to integrate the given function to find the position function? I know that v = Δx/Δt, so we should have:

dx/dt = vi/(1 + kvit)
then we need to take the definite integral from x0 to xf or just 0 to xf. My calculus is a bit rough, but isn't this some sort of a separable differential equation? So we need to make all the x's and t's all on one side? Right now that seems, well, impossible since we have no x's? So do I need to find something involving v and x, then relate/substitute so I only have x's and t's? Help please...

2. Oct 5, 2011

Staff: Mentor

Yes, integrate dx/dt = vi/(1 + kvit)

k and vi are constants, so this is of the basic form 1/(1 + a.t)
and you just integrate with respect to t.

3. Oct 5, 2011

Cryptologica

Ok, thanks!

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook


text:
# Given below are two statements:

Question:

Given below are two statements:

Statement I : Potassium permanganate on heating at $573 \mathrm{~K}$ forms potassium manganate.

Statement II : Both potassium permanganate and potassium manganate are tetrahedral and paramagnetic in nature.

In the light of the above statements, choose the most appropriate answer from the options given below:

1. Statement I is true but statement II is false

2. Both statement I and statement II are true

3. Statement I is false but statement II is true

4. Both statement I and statement II are false

Correct Option: 1

Solution:

Leave a comment


text:
D. Three Integers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three integers $a \le b \le c$.

In one move, you can add $+1$ or $-1$ to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.

You have to perform the minimum number of such operations in order to obtain three integers $A \le B \le C$ such that $B$ is divisible by $A$ and $C$ is divisible by $B$.

You have to answer $t$ independent test cases.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The next $t$ lines describe test cases. Each test case is given on a separate line as three space-separated integers $a, b$ and $c$ ($1 \le a \le b \le c \le 10^4$).

Output

For each test case, print the answer. In the first line print $res$ — the minimum number of operations you have to perform to obtain three integers $A \le B \le C$ such that $B$ is divisible by $A$ and $C$ is divisible by $B$. On the second line print any suitable triple $A, B$ and $C$.

Example
Input
8
1 2 3
123 321 456
5 10 15
15 18 21
100 100 101
1 22 29
3 19 38
6 30 46

Output
1
1 1 3
102
114 228 456
4
4 8 16
6
18 18 18
1
100 100 100
7
1 22 22
2
1 19 38
8
6 24 48


text:
# Completion of a metric space

Let $R$ be a topological ring (i.e addition and product are continuous) which we assume it is metrizable with metric d and consider the completion $\hat{R}$ of the ring $R$ defined as the set of all classes of equivalent Cauchy sequences. Question: why is the completion of $\hat{R}$ (defined in this way) also a topological ring?

It is certainly metrizable by the standard metric: $\hat{R}$, $\hat{d}([(x_{n})],[(y_{n})])=\operatorname{lim} d(x_{n},y_{n})$.

To check addition is continuous: suppose $([(x_{n})],[(y_{n})])$ is a sequence of elements in $\hat{R} \times \hat{R}$ such that$([(x_{n})],[(y_{n})]) \rightarrow ([x],[y])$ then by by definition of convergence in a metric product space we have that:

$[(x_{n})] \rightarrow [x]$ and $[(y_{n})] \rightarrow y$

Therefore $d(x_n,x) \rightarrow 0$ and $d(y_n,y) \rightarrow 0$ as $n \rightarrow \infty$. Since we are in metric spaces this says $x_{n} \rightarrow x$ and $y_{n} \rightarrow y$ as $n \rightarrow \infty$. By assumption $R \times R$ is continuous with respect addition so $x_{n} + y_{n} \rightarrow x+y$.

But then $\hat{d}([(x_{n}+y_{n})])=[x+y]$ so we have that addition is continuous.

Is this OK?

-

This is false if you don't posit some additional relationship between the metric and the structure maps of the ring beyond that they are continuous. Consider $\mathbb{R}$ equipped with the metric $$d(x, y) = |\arctan x - \arctan y|$$

(where $\arctan x \in (-\frac{\pi}{2}, \frac{\pi}{2})$). This induces the same topology as the usual metric so addition and multiplication are still continuous, but the completion with respect to this metric is the extended real line $\mathbb{R} \cup \{ +\infty, -\infty \}$ and it is not possible to extend either the addition or the multiplication.

By assumption $R \times R$ is continuous with respect addition so $x_n + y_n \to x + y$.

$x + y$ is not well-defined at this step in the argument if either $x$ or $y$ does not lie in $R$. What you probably meant is something like this: the sum of Cauchy sequences is Cauchy, so we can define $x + y$ by taking $\lim (x_n + y_n)$.

Unfortunately, the continuity of addition does not guarantee that the sum of Cauchy sequences is Cauchy; in the above example, take $$x_n = (-1)^n + n, y_n = (-1)^n - n.$$

Even when the sum of two Cauchy sequences is Cauchy, it's false that $\lim (x_n + y_n)$ is uniquely determined by $\lim x_n$ and $\lim y_n$; to see this, take $$x_n = -n, y_n = n, x_n = -n, y_n = n^2.$$

Edit: for the $I$-adic completion things are considerably simpler because we can write $d(x, y) = |x - y|$ for some function $| \cdot | : A \to \mathbb{R}$ satisfying (among other things) $|x + y| \le |x| + |y|$ and $|xy| \le |x| |y|$. These properties readily imply all of the nice properties that you want.

In my opinion the conceptually cleanest way to think about $I$-adic completion is not using Cauchy sequences but as follows: the $I$-adic completion is the inverse limit of the quotients $R/I^n$.

-
Perhaps one should assume that addition and multiplication are uniformly continuous. –  Nate Eldredge Apr 10 '12 at 2:32
@Nate: yes, this seems like a good idea. –  Qiaochu Yuan Apr 10 '12 at 2:34
@Mertier: with those extra properties all of the arguments that didn't work before work now. Just try it! It's a nice exercise to show that sums and products of Cauchy sequences are Cauchy with these extra properties and then you can try to prove that sum and product are well-defined on the completion. –  Qiaochu Yuan Apr 10 '12 at 3:29
@Qiaochu Yuan: I get confused. Why showing sum and product are well defined implies continuity? please don't think I want you to solve my problem I just want to understand what exactly I need to prove and this is what confuses me. –  Mertier R. Apr 10 '12 at 6:56
@Mertier: well, I assume you want to prove that the $I$-adic completion is a topological ring? So show that the sum and product of Cauchy sequences is Cauchy, show that the limits of a sum and product depend only on the limits of the summands and productands, show that they are continuous in the $I$-adic topology. Right? –  Qiaochu Yuan Apr 10 '12 at 16:21


text:
# How to draw HUD in DirectX12?

I would like to draw reference frame to see how my camera moves around scene. I want these arrows to always be on the top of other geometry. How can I achieve it?

I think I need to disable depth test for this draw calls. Should I use just another PSO with changed DepthStencilState?

EDIT: Well, it works for me like that.

// opaquePsoDesc defined somewhere above
D3D12_GRAPHICS_PIPELINE_STATE_DESC opaqueHudPsoDesc = opaquePsoDesc;
opaqueHudPsoDesc.DepthStencilState.DepthEnable = false;
THROW_IF_FAILED(g_device->CreateGraphicsPipelineState(&opaqueHudPsoDesc, IID_PPV_ARGS(&psos_["opaque_HUD"])));

And then before drawing your HUD you can:

commandList->SetPipelineState(psos_["opaque_HUD"].Get());

I'll leave this answer here, in case someone will need it.

Well, that works fine if you don't want depth test for the HUD objects.

• You can actually post an answer to your own question and close it yourself. That way it doesn't stay open and unanswered :) – Honeybunch Dec 31 '16 at 19:46

See DirectX Tool Kit for DirectX 12 and in particular the SpriteFont and SpriteBatch classes.


text:
# zbMATH — the first resource for mathematics

Disks vs. spheres: Contrasting properties of random packings. (English) Zbl 0935.82521
Summary: Collections of random packings of rigid disks and spheres have been generated by computer using a previously described concurrent algorithm. Particles begin as infinitesimal moving points, grow in size at a uniform rate, undergo energy-nonconserving collisions, and eventually jam up. Periodic boundary conditions apply, and various numbers of particles have been considered ($$N\leq 2000$$ for disks, $$N\leq 8000$$ for spheres). The irregular disk packings thus formed are clearly polycrystalline with mean grain size dependent upon particle growth rate. By contrast, the sphere packings show a homogeneously amorphous texture substantially devoid of crystalline grains. This distinction strongly intluences the respective results for packing pair correlation functions and for the distributions of particles by contact number. Rapidly grown disk packings display occasional vacancies within the crystalline grains; no comparable voids of such distinctive size have been found in the random sphere packings. “Rattler” particles free to move locally but imprisoned by jammed neighbors occur in both the disk and sphere packings.

##### MSC:
 82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics 52C17 Packing and covering in $$n$$ dimensions (aspects of discrete geometry) 82D30 Statistical mechanical studies of random media, disordered materials (including liquid crystals and spin glasses)
Full Text:
##### References:
 [1] B. D. Lubachevsky and F. H. Stillinger,J. Stat. Phys. 60:561 (1990). · Zbl 1086.82569 · doi:10.1007/BF01025983 [2] C. H. Bennett,J. Appl. Phys. 43:2727 (1972). · doi:10.1063/1.1661585 [3] D. J. Adams and A. J. Matheson,J. Chem. Phys. 56:1989 (1972). · doi:10.1063/1.1677488 [4] W. M. Visscher and M. Bolsterli,Nature 239:504 (1972). · doi:10.1038/239504a0 [5] A. J. Matheson,J. Phys. C 7:2569 (1974). · doi:10.1088/0022-3719/7/15/007 [6] P. Mrafko and P. Duhaj,Phys. Stat. Sol. (a) 23:583 (1974). · doi:10.1002/pssa.2210230230 [7] T. Ichikawa,Phys. Stat. Sol. (a) 29:293 (1975). · doi:10.1002/pssa.2210290132 [8] F. Delyon and Y. E. Lévy,J. Phys. A 23:4471 (1990). · doi:10.1088/0305-4470/23/20/009 [9] G. Mason,Disc. Faraday Soc. 43:75 (1967). · doi:10.1039/df9674300075 [10] J. L. Finney,Mater. Sci. Eng. 23:199 (1976). · doi:10.1016/0025-5416(76)90194-4 [11] E. L. Hinrichsen, J. Feder, and T. Jossang,Phys. Rev. A 41:4199 (1990). · doi:10.1103/PhysRevA.41.4199 [12] B. D. Lubachevsky,J. Comp. Phys. 94:255 (1991). · Zbl 0716.68094 · doi:10.1016/0021-9991(91)90222-7 [13] H. L. Frisch,Adv. Chem. Phys. 6:229 (1964). · doi:10.1002/9780470143520.ch5 [14] F. H. Stillinger and Z. W. Salsburg,J. Stat. Phys. 1:179 (1969). · doi:10.1007/BF01007250 [15] D. Ruelle and Ya. G. Sinai,Physica 140A:1 (1986). [16] J. L. Finney,Nature 266:309 (1977). · doi:10.1038/266309a0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
### Introduction

Have you ever noticed that when a train or car moves past you rapidly its whistle or horn seems to change to a lower note? In 1842 an Austrian Physicist, Hans Christian Doppler, asserted that sound waves emitted by a moving train would have a higher frequency when moving toward a listener and a lower frequency when moving away. For surface waves in water, Doppler predicted the same type of frequency shift. In particular, a decrease in the frequency of waves propagating behind a source that moves away at a speed vs can be predicted using the Doppler equation

${f_{\text{B}}} = {f_0}\frac{{{v_{\text{w}}}}} {{{v_{\text{w}}} + {v_{\text{s}}}}}$

where vw is the speed of wave propagation in water and f0 is the frequency of the waves created by a stationary source. Doppler also predicted that the frequency increase in front of a source is given by

${f_{\text{F}}} = {f_0}\frac{{{v_{\text{w}}}}} {{{v_{\text{w}}} - {v_{\text{s}}}}}$

### Objectives

In this activity, you will

• Verify the Doppler Equations for surface waves in water by using Logger Pro to analyze two high speed movies.


text:
# Number Theory / Representation Theory Seminar, University of Wisconsin - Madison

• When: Thursdays, 2:30 PM – 3:30 PM
• Where: Van Vleck B113
• Please join the NT/RT mailing list: (you must be on a math department computer to use this link).

There is also an accompanying graduate-level seminar, which meets on Tuesdays.

You can find our Fall 2018 speakers in Fall 2018.
You can find our previous speakers in Spring 2018.

# Spring 2019 Semester

 Date Speaker (click for homepage) Title (click for abstract) Jan 23 Wed. Room VV B231 Yunqing Tang (Princeton University) Reductions of abelian surfaces over global function fields Jan 24 Hassan-Mao-Smith--Zhu The diophantine exponent of the $\mathbb{Z}/q\mathbb{Z}$ points of $S^{d-2}\subset S^d$ Jan 31 Kyle Pratt (University of Illinois at Urbana-Champaign) Breaking the $\frac{1}{2}$-barrier for the twisted second moment of Dirichlet $L$-functions Feb 7 Shamgar Gurevich (UW-Madison) Harmonic Analysis on $GL_n$ over finite fields Feb 14 Tonghai Yang (UW-Madison) The Lambda invariant and its CM values Feb 21 No Seminar Feb 28 Brian Lawrence (the University of Chicago) Diophantine problems and a p-adic period map. March 7 Masoud Zargar (Regensburg) Sections of quadrics over the affine line March 14 Elena Mantovan (Caltech) p-adic automorphic forms, differential operators and Galois representations March 21 Spring Break March 28 Adebisi Agboola (UCSB) Relative K-groups and rings of integers April 4 Wei-Lun Tsai (Texas A&M University) Hecke L-functions and $\ell$ torsion in class groups April 11 Taylor McAdam (UCSD) April 18 Ila Varma (UCSD) April 25 Jen Berg (Rice University) May 2 Melanie Wood (UW-Madison) May 9 David Zureick-Brown (Emory College of Arts and Sciences)

*to be confirmed


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Journal history Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Fundam. Prikl. Mat.: Year: Volume: Issue: Page: Find

 Fundam. Prikl. Mat., 2012, Volume 17, Issue 8, Pages 31–34 (Mi fpm1468)

On a problem related to homomorphism groups in the theory of Abelian groups

S. Ya. Grinshpon

Tomsk State University

Abstract: In this paper, for any reduced Abelian group $A$ whose torsion-free rank is infinite, we construct a countable set $\mathfrak A(A)$ of Abelian groups connected with the group $A$ in a definite way and such that for any two different groups $B$ and $C$ from the set $\mathfrak A(A)$ the groups $B$ and $C$ are isomorphic but $\operatorname{Hom}(B, X)\cong\operatorname{Hom}(C, X)$ for any Abelian group $X$. The construction of such a set of Abelian groups is closely connected with Problem 34 from L. Fuchs' book “Infinite Abelian Groups”, Vol. 1.

Full text: PDF file (85 kB)
References: PDF file   HTML file

English version:
Journal of Mathematical Sciences (New York), 2014, 197:5, 602–604

UDC: 512.541

Citation: S. Ya. Grinshpon, “On a problem related to homomorphism groups in the theory of Abelian groups”, Fundam. Prikl. Mat., 17:8 (2012), 31–34; J. Math. Sci., 197:5 (2014), 602–604

Citation in format AMSBIB
\Bibitem{Gri12} \by S.~Ya.~Grinshpon \paper On a~problem related to homomorphism groups in the theory of Abelian groups \jour Fundam. Prikl. Mat. \yr 2012 \vol 17 \issue 8 \pages 31--34 \mathnet{http://mi.mathnet.ru/fpm1468} \transl \jour J. Math. Sci. \yr 2014 \vol 197 \issue 5 \pages 602--604 \crossref{https://doi.org/10.1007/s10958-014-1741-2} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84893844333}


text:
Accelerating the pace of engineering and science

# gdare

Generalized solver for discrete-time algebraic Riccati equation

## Syntax

[X,L,report] = gdare(H,J,ns)
[X1,X2,D,L] = gdare(H,J,NS,'factor')

## Description

[X,L,report] = gdare(H,J,ns) computes the unique stabilizing solution X of the discrete-time algebraic Riccati equation associated with a Symplectic pencil of the form

$H-tJ=\left[\begin{array}{ccc}A& F& B\\ -Q& E\prime & -S\\ S\prime & 0& R\end{array}\right]-\left[\begin{array}{ccc}E& 0& 0\\ 0& A\prime & 0\\ 0& B\prime & 0\end{array}\right]$

The third input ns is the row size of the A matrix.

Optionally, gdare returns the vector L of closed-loop eigenvalues and a diagnosis report with value:

• -1 if the Symplectic pencil has eigenvalues on the unit circle

• -2 if there is no finite stabilizing solution X

• 0 if a finite stabilizing solution X exists

This syntax does not issue any error message when X fails to exist.

[X1,X2,D,L] = gdare(H,J,NS,'factor') returns two matrices X1, X2 and a diagonal scaling matrix D such that X = D*(X2/X1)*D. The vector L contains the closed-loop eigenvalues. All outputs are empty when the Symplectic pencil has eigenvalues on the unit circle.


text:
# Points on the coordinate plane

Practice plotting points like (-2, 4).

### Problem

Which ordered pair is not graphed below?
Please choose from one of the following options.
Get first 1 correct, or 5 in a row.


text:
## Tag Archives: mathematics

### The Peace of Liberal Education

The wall of Dolmabahçe Sarayı, January 11, 2015

The occasion of this article is my discovery of a published Turkish translation of Collingwood’s Speculum Mentis or The Map of Knowledge (Oxford, 1924). Published as Speculum Mentis ya da Bilginin Haritası (Ankara: Doğu Batı, 2014), the translation is by Kubilay Aysevenler and Zerrin Eren. Near the end of the book, Collingwood writes the following paragraph about education, or what I would call more precisely liberal education. The main purpose of this article then is to offer the paragraph to any reader who happens to stop by.

### Bosphorus Sky

This is about the morning of Thursday, December 18, 2014, a morning I spent by the Bosphorus, thinking mostly about poetry, and photographing the sky.

### Şirince 2014

This is about our second visit to the Nesin Mathematical Village in Şirince this year. The first visit was to attend the Summer School Around Valuation Theory, May 22–26. Now we have come back to teach, as usual, in the Turkish Mathematical Society Undergraduate and Graduate Summer School. This time we are teaching not just one week, but two: July 14–27. My own course, as several times in the past, is on nonstandard analysis. Each course meets every day but Thursday, two hours a day.

The Math Village only increases in beauty every year, as I mean to suggest by posting a few photographs below.

I shall also state an opinion. The summer school here in the Village used to receive some funding from TÜBİTAK (the Scientific and Technological Research Council of Turkey); but apparently this funding is no longer forthcoming. Nonetheless, the Nesin Mathematical Village is the kind of venture that governments at their best will support. Certain Libertarians, desiring minimal government, still want government to maintain property rights, so that citizens can make money. Other people look to government to create jobs more directly. But money by itself is worthless, and some jobs are more worth doing than others. I do not say that the Nesin Mathematical Village should be supported for the technological gains that mathematics can make possible. I say that participating in the activities of the Village is itself a gain. What are you going to do when your basic animal needs are satisfied? You could do a lot worse than spend time on mathematics.

### NL V: “The Ambiguity of Feeling”

Index to this series

Feeling differs from thought. Thought is founded in feeling; thought is erected on feeling; thought needs feeling. Thought needs feelings that are strong enough to support it. But thought itself is not strong (or weak); it has (or can have) other properties, like precision and definiteness. Thought can be remembered and shared in a way that feeling cannot.

The New Leviathan is a work of thought. It might be said that a work of thought cannot properly explain feeling. Collingwood more or less says this in Chapter V, even in its very title: “The Ambiguity of Feeling.” Continue reading

### NL III: “Body As Mind”

Index to this series

In Chapter I of The New Leviathan, we stipulated that natural science, the “science of body,” must be free to pursue its own aims. But we ourselves are doing science of mind, and:

1. 85. The sciences of mind, unless they preach error or confuse the issue by dishonest or involuntary obscurity, can tell us nothing but what each can verify for himself by reflecting on his own mind.

All of us can be scientists of mind, if only we are capable of reflection: Continue reading

### NL II: “The Relation Between Body and Mind”

Index to this series

I continue making notes on The New Leviathan (1942) of R. G. Collingwood (1889–1943). Now my main concern is with the second chapter, “The Relation Between Body and Mind”; but again I shall range widely.

### Preliminaries

Some writers begin with an outline, which they proceed to fill out with words. At least, they do this if they do what they are taught in school:

He showed how the aspect of Quality called unity, the hanging-togetherness of a story, could be improved with a technique called an outline. The authority of an argument could be jacked up with a technique called footnotes, which gives authoritative reference. Outlines and footnotes are standard things taught in all freshman composition classes, but now as devices for improving Quality they had a purpose.

Thus Robert Pirsig, Zen and the Art of Motorcycle Maintenance, ch. 17. Does anybody strictly follow the textbook method? Continue reading

### Learning mathematics

This is mostly reminiscences about high school. I also give some opinions about how mathematics ought to be learned. This article originally formed one piece with my last article, “Limits”.

I learned calculus, and the epsilon-delta definition of limit, in Washington D.C., in the last two years of high school, in a course taught by a peculiar fellow named Donald J. Brown. The first of these two years was officially called Precalculus Honors, but some time in that year, we started in on calculus proper. Continue reading

### Limits

This is about limits in mathematics: both the technical notion that arises in calculus, and the barriers to comprehension that one might reach in one’s own studies. I am going to say a few technical things about the technical notion, but there is no reason why this should be a barrier to your reading: you can just skip the paragraphs that have special symbols in them.

Looking up something else in the online magazine called Slate, I noted a reprint of an article called “What It Feels Like to Be Bad at Math” from a blog called Math With Bad Drawings by Ben Orlin. Now teaching high-school mathematics, Mr Orlin recalls his difficulties in an undergraduate topology course. His memories help him understand the difficulties of his own students. When students do not study, why is this? It is because studying makes them conscious of how much they do not understand. They feel stupid, and they do not like this feeling. Continue reading

### Self-similarity

From the poster depicting a few von Neumann natural numbers, I created this animation. The moving image no longer depicts natural numbers in the sense of the poster, since there is no infinite descending chain of natural numbers. There is an infinite ascending chain of them; but the poster does not actually depict such a chain as nested circles. So running the animation in reverse would not give a correct suggestion of the original poster, even if it were of infinite size. Continue reading

### The von Neumann natural numbers: a fractal-like image

See the next article, “Self-similarity,” for an animation of the image here.

I have long been fascinated by von Neumann’s definition of the natural numbers (and more generally the ordinals). In developing axioms for set theory, Zermelo used the sets $0$, $\{0\}$, $\{\{0\}\}$, $\{\{\{0\}\}\}$, $\{\{\{\{0\}\}\}\}$, and so on as the natural numbers. Here $0$ is the empty set. Zermelo’s method works, but is not so elegant as von Neumann’s later proposal to consider each natural number as the set of all natural numbers that are less than it is, so that (again) $0$ is the empty set, but also $n+1=\{0,1,\dots,n\}$. Continue reading